扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 数学建模困难
单选题
2013年5月第37题
收藏
分享
#数学与经济管理
#数学建模
#凯恩建议了解即可
#教材之外（超纲）
某乡规划了村村通公路网建设方案连接其所属6个村，每两个村之间至多只有一条公路相连，各条公路互不重叠。因此，各村所连接的公路条数形成一个6数序列。以下4个序列中，除（__）外都是不可能的。
问题（1）
正确答案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选项分析过程如表所示。
