扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 数学建模困难
单选题
2013年5月第37题
困难
单选题
2013年5月第37题
#了解即可
#超纲
某乡规划了村村通公路网建设方案连接其所属6个村，每两个村之间至多只有一条公路相连，各条公路互不重叠。因此，各村所连接的公路条数形成一个6数序列。以下4个序列中，除（__）外都是不可能的。
问题（1）
浓缩知识点
无向简单图度序列可图性判定核心知识点：
- 基础必要筛选条件：一是握手定理，所有顶点度数之和必为偶数，因为每条边会为两个顶点各贡献1个度数；二是单个顶点的度数最大值不能超过总顶点数减1，因为每个顶点最多与其余所有顶点相连，可通过这两点快速排除不符合的序列。
- 充要判定方法一：Havel–Hakimi消去法，操作步骤为将序列按非递增顺序排列，移除最大度数d，对剩余序列的前d个度数分别减1，重复该过程，若最终能转化为全0序列，则该序列可图，若过程中出现负数则不可图，操作中需及时重排序列保持非递增状态，方便后续步骤。
- 充要判定方法二：Erdős–Gallai判据，对非递增排序的度序列d₁≥d₂≥…≥dₙ，需同时满足两个条件：总度数和为偶数；对每个1≤k≤n，前k个度数之和≤k(k-1)+Σ（从i=k+1到n）min(dᵢ,k)，满足则序列可对应真实存在的无向简单图。
- 应用场景：这类判定方法可用于网络拓扑规划、图结构建模等场景，比如验证通信网络、交通路网的节点连接方案是否具备可行性。
正确答案
D
本题考察的是图论中的度序列可图性判定，
常用方法为握手定理（度和为偶数）与Havel–Hakimi 消去法（或 Erdős–Gallai 判据）。思路：先用握手定理快速排除，再用 Havel–Hakimi 判断是否能化为全 0 序列。
A选项 5，4，3，3，2，2：度和为 5+4+3+3+2+2=19，为奇数，违反握手定理：无向简单图所有顶点度数之和必为偶数，不可能。
B选项 5，5，4，3，2，1：度和为20为偶数，但用Havel–Hakimi：
取5，消去后得 [4,3,2,1,0]；再取4，需对后面4个减1，得到 [2,1,0,-1] 出现负数，故不可能。
C选项 5，4，4，3，1，1：度和为18为偶数，继续Havel–Hakimi：
取5，得 [3,3,2,0,0]；取3，需对后面3个减1，得到 [2,1,-1,0] 出现负数，故不可能。
D选项 5，4，4，3，2，2：度和为20为偶数，继续Havel–Hakimi：
取5，得 [3,3,2,1,1]；取3，得 [2,1,0,1]→重排为 [2,1,1,0]；取2，得 [0,0,0]，成功化为全 0 序列，可图，因此是唯一可能的序列。
具体做法如下图所示：以B选项为例，分析过程如表所示。
接下来使用同样的方法分析C选项，分析过程如表所示。
D选项分析过程如表所示。
