Question

同学们野营时建了9个营地，连接营地之间的道路如图所示．贝贝要给每个营地插上一面旗帜，要求相邻营地的旗帜色彩不同，则贝贝最少需要

3

种颜色的旗子．如果贝贝从某营地出发，（填“能”或“不能”）不走重复的路就

不能

完成这项任务．

Answer 1

分析：（1）从中间的三点考虑；
（2）从奇点的个数考虑，如果奇点的个数为偶数，不走重复的路就不能完成任务，如果奇点的个数为奇数，不走重复的路就能完成任务．

解答：解：因为中间的三点连成一个三角形，这三点所代表的营地两两相邻，要使相邻营地没有相同颜色的旗子，必须各插一种与其它两点不同颜色的旗子，所以最少需要3种颜色的旗子．
因为本题共有6个奇点，即偶数个奇点，不走重复路线不能完成插旗的任务．
故答案为：3，不能．

点评：此题考查了排列组合知识，以及一笔画定理：①凡是由偶点组成的连通图，一定可以一笔画成．画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图；②凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成．画时必须把一个奇点为起点，另一个奇点终点；③其他情况的图都不能一笔画出．（有偶数个奇点除以二便可算出此图需几笔画成．）