某乡规划了村村通公路网建设方案连接其所属6个村,每两个村之间至多只有一条公路相连

资格题库2022-08-02  58

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

选项 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

解析 本题是一个图论的问题。每一个村庄所连接的公路条数就是这个村庄结点的度。在一个图中,所有结点度之和应为偶数(因为任意一条边会产生2度),所以首先可以排除A选项。对B、C、D三个选项进行分析时,需要有一定的图论基础知识。题目要求分析选项中的序列是否可能存在,其实是问大家,这样的度的序列是否能构成合法的图。由于结点很多,我们不能很快识别出图的合法性。但可以考虑将问题简化,简化时的依据为“如果某图是一个合法的图,那么我们去除图中的结点,并将与该结点相连的所有线去除,仍应得到一个合法的图。”以B选项为例,分析过程如表所示。 表1-1 B选项分析过程接下来使用同样的方法分析C选项,分析过程如表所示。表1-2 C选项分析过程D选项分析过程如表所示。表1-3 D选项分析过程
转载请注明原文地址:https://tihaiku.com/congyezige/2401519.html

最新回复(0)