单选题 某乡规划了村村通公路网建设方案连接其所属6个村,每两个村之间至多只有一条公路相连,各条公路互不重叠。因此,各村所连接的公路条数形成一个6数序列。以下4个序列中,除______外都是不可能的。
【正确答案】 D
【答案解析】本题是一个图论的问题。
每一个村庄所连接的公路条数就是这个村庄节点的度。在一个图中,所有节点度之和应为偶数(因为任意一条边会产生2度),所以首先可以排除A选项。
对B、C、D三个选项进行分析时,需要有一定的图论基础知识。题目要求分析选项中的序列是否可能存在,其实是问大家,这样的度的序列是否能构成合法的图。由于节点很多,我们不能很快识别出图的合法性。但可以考虑将问题简化,简化时的依据为“如果某图是一个合法的图,那么我们去除图中的节点,并将与该节点相连的所有线去除,仍应得到一个合法的图”。
以B选项为例,分析过程如表1所示。
表1 B选项分析过程
A B C D E F 说明
初始序列 5 5 4 3 2 1
去掉A后 4 3 2 1 0 由于A的度为5,说明A与除自己外的其他5个节
点有连线,所以去掉A的同时,需要将B~F的度
均减1
去掉B后 2 1 0 -1 同理,去掉B节点时,需要将它与C~F的连线去
除。此时可以发现,F的度已为-1,这说明该序列
无法组成合法图
接下来使用同样的方法分析C选项,分析过程如表2所示。
表2 C选项分析过程
A B C D E F 说明
初始序列 5 4 4 3 1 1
去掉A后 3 3 2 0 0 由于A的度为5,说明A与除自己外的其他5个节
点有连线,所以去掉A的同时,需要将B~F的度
均减1
去掉B后 2 1 -1 0 同理,去掉B节点时,需要将它与其他3个点相连
的线去除,但无论如何进行选择,都将出现节点度
为-1的情况,这样就形成了非法的图
D选项分析过程如表3所示。
表3 D选项分析过程
A B C D E F 说明
初始序列 5 4 4 3 2 2
去掉A后 3 3 2 1 1 由于A的度为5,说明A与除自己外的其他5个节
点有连线,所以去掉A的同时,需要将B~F的度
均减1
去掉B后 2 1 0 1 同理,去掉B节点时,需要将它与其他3个点相连
的线去除,此时可选CDE(也可选DEF、CDF等)
去掉C后 0 0 0 此时,所有节点连线均被去除,仍属于合法的图