离散数学习题三参考答案

离散数学习题三参考答案

第三节 图论

1.画出所有4个顶点的简单图。

解：本题这考虑连通图的情况。共有5个不同构的图。

2.在某次宴会上，许多人互相握手，证明奇数次握手的人一定是偶数个。 解：设每个人看成一个顶点，两人握手看成两顶点间的一条边，每人握手的次数就是该顶点的度数，由定理1的推论2马上可得结论。

3.设图G＝（V，E）中有12条边，已知G中3度顶点的有3个，其余顶点的度数均小于3，问G中至少有多少个顶点？为什么？

解：如图G不是连通图，那么12条边最多的顶点数是12×2=24；一个顶点的度数是3，则要减去2个顶点数，所以3度顶点的有3个，就要减去2×3-6个顶点；同样一个顶点的度数是2，则要减去1个顶点数；为了使顶点数最小，图必须是连通图，所以顶点数为2的顶点的个数是（12×2-3×3）÷2的整数部分等于7个，有一个顶点的度数是1，所以G中至少有的顶点数是3+7+1=11（个）。 4.n个运动队之间安排一项比赛，已赛完了n+1场，求证：一定存在这样一个队，它已经至少参加了3场比赛。

解：如果每个运动队都只赛了2场，则共赛了2n÷2=n

5.下图表示用堤埂分割成很多小块的水稻田。为了用水灌溉需要挖开一些堤埂（不能挖堤埂的交点）。问最少要挖开多少条堤埂，才能使水浇灌到每小块稻田？

第五题

解：把每块田看成顶点，相邻的田同一条边连接，这题就是最小生成树问题。

因为有12块田地，所以最少要挖开11条堤埂，才能使水浇灌到每小块稻田。（见上右图）

6在下列图中，求一条欧拉通路。

解：略

7.证明：若G=〈V，E〉是简单图，则m≤Cn2 ，其中m为图的边数，n为图的顶点数。（7，9一样）

解：顶点数相同的情况下，简单图的边数一定小于完全图的边数。

8.设G是一个连通图，不含奇数点，证明：从G中任意去掉一条边，得到的图

仍是连通图。

解：G是一个连通图，不含奇数点，所以其所有顶点的度数均大于2，就是任何一个顶点至少有两条边与其他顶点相邻。去掉一条边，则两个顶点与其他顶点至少还有一条边与其他顶点相邻，所以还是通路图。

9.证明：若G=〈V，E〉是简单图，则m≤Cn2 ，其中m为图的边数，n为图的顶点数。

10.证明：设图G是一棵树，则图G中最长通路的起点和终点的度数均为1。 证：倘如最长通路的起点和终点的度数有一个大于1，则至少有两条边在起点（或终点）相邻。那么至少有一条边不是这通路上的边，（因为是端点），加上这条边，仍然是一条通路（因为是树，不可能成圈），并比前一条通路要长，与最长通路矛盾。

11.求下列各图中最小生成树。

第11题

解：用破圈法即可得，见上右图：。

12.设有邮路图如下：问邮递员应按怎样的路线行走才能 使所行的路程最短？（设邮局为A）

（第12题图）

解：A→B→C→A→C→D→A→E→D→E→F→A，见上右图。

重复走了两段AC和 DF，多走了2+4=6个单位。 13.求出下图中从v1到其他各点的最短通路。

（第13题图） 解：见上右图。 14.在完全图Kn中，（1）任意两点间有多少条边？ （2）有多少个圈？

（3）包含某条边e的圈有多少个？ 解：（1）任意两点间有1条边；

134n?Cn???Cn?2n?1?n?n(n?1)个圈； （2）有Cn2

12n?1n?1（3）包含某条边e的圈有Cn?C???C?2?1个。 ?2n?2n?1

15. 若图G=中存在一条包含G的所有顶点的通路，则此通路称为哈密尔顿通路。如存在一个包含G的所有顶点的圈，则这个圈为G的哈密尔顿圈。图G就称为哈密尔顿图。

证明：完全图是哈密尔顿图。

证明：因为完全图可以找到一条通路通过所有顶点。

16.某人从A出发到B，C，D，E四地去旅游，在回到A，各地间的路程如下图：

第16题 问应如何选择旅游路线，使总路程最短？

解：A→B→E→D→C→A 即 7+7+2+3+5=24（见上右图）。 17.下列各图是否是两步图？

第17题

解：三个都是，见下图。

18.已知关于人员a，b，c，d，e，f的下述事实： a 会说汉语，法语和日语； b 会说德语，俄语和日语； c 会说英语和法语； d 会说汉语和西班牙语； e 会说英语和德语； f 会说俄语和西班牙语，

试问能否把这六人分成两组，使同组中没有两人能互相交谈？

解：能，见图。

19.有5个工人分配5个工种，要求每个工种配一个工人，每个工人可以做的工

种如下表：

工种 1 2 3 4 5 工号 1 能 不能 不能 能 不能

2 能 不能 不能 不能 能 3 不能 能 不能 能 能 4 能 不能 能 不能 能 5 不能 不能 能 能 能

能否有合适的安排，使得每项工作都有人做？

解：能，见图。

20.现有四个工人Ai 和四种零件Bj，工人Ai加工零件Bj所得的收益为Wij由下表给出，

工种 B1 B2 B3 B4 工号 A1 5 9 2 7 A2 3 4 3 5 A3 6 7 7 3 A4 6 10 3 4

问应怎样安排加工任务，使每个工人加工一种零件，一个零件由一个工人加工，且使工人们的总收益最大？

解：

所以M?{(x1,y1)(x4,y2)(x3,y3)(x2,y4）} 最大收益值为5+10+7+5=27

本文来源：https://www.bwwdw.com/article/w1xf.html