某乡规划了村村通公路网建设方案连接其所属6个村,每两个村之间至多只有一条公路相连,各条公路互不重叠。因此,各村所连接的公路条数形成一个6数序列。以下4个序列中,除________外都是不可能的。

admin2014-08-23  35

问题 某乡规划了村村通公路网建设方案连接其所属6个村,每两个村之间至多只有一条公路相连,各条公路互不重叠。因此,各村所连接的公路条数形成一个6数序列。以下4个序列中,除________外都是不可能的。

选项 A、5,4,3,3,2,2
B、5,5,4,3,2,1
C、5,4,4,3,1,1
D、5,4,4,3,2,2

答案D

解析 本题考查应用数学(图论)知识。每条公路在序列中都被计算两次,因此,6数序列的总和应是偶数。供选答案A中各数之和为奇数,所以不可能。供选答案B中的前两数5表示有两个村与其他各村都有公路相连,因此不可能存在只有l条公路的村,所以B也不可能。供选答案C中最后1村只有1条公路,而第1村与其他各村都相连,因此这两个村之间有公路连接。不算这两村及其间的公路后,形成5个村和5数序列4,4,4,3,1。该序列中,既然前3村中每村都与其他4村都相连,那么,每个村的公路数至少为3,所以C也是不可能的。D是可能的,如下图,其中各村公路的条数为:A-5,B-2,C-3,D-4,E-2,F-4。
转载请注明原文地址:https://kaotiyun.com/show/YWLZ777K
0

最新回复(0)