2. 从业资格
  3. 某乡规划了村村通公路网建设方案连接其所属6个村，每两个村之间至多只有一条公路相连

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

资格题库2022-08-02  66
问题 某乡规划了村村通公路网建设方案连接其所属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)