2017同等学力申硕计算机训练题4-3
来源：新东方在线
时间：2017-01-31 15:54:21
备考2017同等学力申硕的考生，小编整理一些计算机训练题供大家练习，希望能帮助大家更好的复习。
1. 证明或推翻下列命题：“设平面上有 100 个点，其中任意两点间的距离至少是1，则最多有300 对点距离恰好是1”。
解答与评分标准：
命题成立(2 分)。
无向图 G=，V 是平面上的这100 个点，两个点相邻当且仅当这两点距离恰好是1(2 分)。
每个顶点的度数不超过 6(3 分)。
根据握手定律(3 分)，
2|E|=顶点度数之和≤100*6, 所以这个图的边数不超过300(2 分)。
2. 所谓 n 维网格就是一个无向图G=，其中V={ | 1≤ij≤mj,1≤j≤n}，E={(v1,v2)| v1 和v2 恰好只在一个坐标上相差1}。讨论当mj 和n 取哪些正整数值时，G 是哈密顿图，并给出证明。
解答与评分标准：
分情况讨论。注意 G 的顶点数是m1*m2*m3*⋯*mn。
(1) 所有mj 都为1：G 是平凡图，是哈密顿图(2 分)。
(2) 恰好有一个mj 大于1：G 是长度大于1 的初级路径，不是哈密顿图(2 分)。
(3) 至少有两个mj 大于1：G 是偶图(无奇数长度回路)(2 分)。
(3a) m1*m2*m3*⋯*mn 是偶数：G 是哈密顿图，用归纳法构造哈密顿回路(2 分)。
(3b) m1*m2*m3*⋯*mn 是奇数：G 不是哈密顿图，偶哈密顿图两部分顶点数相等，总顶点数是偶数(2 分)。
3. 证明或推翻下列命题：“任意给定平面上有限个点，则连接这些点的最短哈密顿回路的长度不超过连接这些点的最小生成树(不添加额外顶点)的长度的2 倍。子图的长度就是这个子图上的边的长度之和。”
解答与评分标准：
命题成立(2 分)。
(课本图论部分最后一章定理)先求最小生成树奇数度顶点之间的“最小”匹配，加入匹配“边”得到欧拉图(3 分)。
沿着欧拉回路前进，“抄近路”避开已经访问过的顶点，就得出哈密顿回路(3 分)。
由于距离的三角形不等式，这条哈密顿回路长度不超过最小生成树长度的2 倍(2 分)。
4. 画出所有非同构的 5 阶根树。
解答与评分标准：
9 种(每种1 分，重复画扣0.5 分，全画10 分)。非同构的5 阶树共有3种，分别选一个顶点做根。
5.证明或推翻下列命题：“设连通简单平面图G 的最小度δ(G)≥4，则G 的点色数χ(G)≥3.”
解答与评分标准：
假设χ(G)<3.(反证法分情况讨论2 分)
χ(G)=1 当且仅当G 为n 阶零图，与已知矛盾。(4 分)
χ(G)=2 当且仅当G 为二部图，因为G 为平面图，只能为K2,s 或Kr,2. 此时必有δ(G)=2, 与已知矛盾。(4 分)
结束
特别声明：①凡本网注明稿件来源为"原创"的，转载必须注明"稿件来源：育路网"，违者将依法追究责任；
②部分稿件来源于网络，如有侵权，请联系我们沟通解决。
阅读全文
一站式择校服务！【免费领取】专业规划&择校方案
500字以内
发送
相关文章推荐
- 考后首发2019年同等学力申硕真题及答案解析
2019年同等学力申硕统考将于5月19日举行，我们将于考后发布2019年同等学力申硕真题及答案解析。以下为2018年同等学力申硕各科
0赞0评论2019-05-15 09:01:06
评论0
“无需登录，可直接评论...”