离散数学习题三参考答案.doc

离散数学习题三参考答案第三节 图论1.画出所有4个顶点的简单图。解：本题这考虑连通图的情况。共有5个不同构的图。2.在某次宴会上，许多人互相握手，证明奇数次握手的人一定是偶数个。解：设每个人看成一个顶点，两人握手看成两顶点间的一条边，每人握手的次数就是该顶点的度数，由定理1的推论2马上可得结论。3.设图G（V，E）中有12条边，已知G中3度顶点的有3个，其余顶点的度数均小于3，问G中至少有多少个顶点？为什么？解：如图G不是连通图，那么12条边最多的顶点数是122=24；一个顶点的度数是3，则要减去2个顶点数，所以3度顶点的有3个，就要减去23-6个顶点；同样一个顶点的度数是2，则要减去1个顶点数；为了使顶点数最小，图必须是连通图，所以顶点数为2的顶点的个数是（122-33）2的整数部分等于7个，有一个顶点的度数是1，所以G中至少有的顶点数是3+7+1=11（个）。4.n个运动队之间安排一项比赛，已赛完了n+1场，求证：一定存在这样一个队，它已经至少参加了3场比赛。解：如果每个运动队都只赛了2场，则共赛了2n2=n<n+1，所以一定存在这样一个队，它已经至少参加了3场比赛。5.下图表示用堤埂分割成很多小块的水稻田。为了用水灌溉需要挖开一些堤埂（不能挖堤埂的交点）。问最少要挖开多少条堤埂，才能使水浇灌到每小块稻田？ 第五题解：把每块田看成顶点，相邻的田同一条边连接，这题就是最小生成树问题。因为有12块田地，所以最少要挖开11条堤埂，才能使水浇灌到每小块稻田。（见上右图）6在下列图中，求一条欧拉通路。解：略7.证明：若G=V，E是简单图，则mCn2 ，其中m为图的边数，n为图的顶点数。（7，9一样）解：顶点数相同的情况下，简单图的边数一定小于完全图的边数。8.设G是一个连通图，不含奇数点，证明：从G中任意去掉一条边，得到的图仍是连通图。解：G是一个连通图，不含奇数点，所以其所有顶点的度数均大于2，就是任何一个顶点至少有两条边与其他顶点相邻。去掉一条边，则两个顶点与其他顶点至少还有一条边与其他顶点相邻，所以还是通路图。9.证明：若G=V，E是简单图，则mCn2 ，其中m为图的边数，n为图的顶点数。10.证明：设图G是一棵树，则图G中最长通路的起点和终点的度数均为1。证：倘如最长通路的起点和终点的度数有一个大于1，则至少有两条边在起点（或终点）相邻。那么至少有一条边不是这通路上的边，（因为是端点），加上这条边，仍然是一条通路（因为是树，不可能成圈），并比前一条通路要长，与最长通路矛盾。11.求下列各图中最小生成树。 第11题解：用破圈法即可得，见上右图：。12.设有邮路图如下：问邮递员应按怎样的路线行走才能 使所行的路程最短？（设邮局为A） （第12题图）解：ABCACDAEDEFA，见上右图。重复走了两段AC和 DF，多走了2+4=6个单位。13.求出下图中从v1到其他各点的最短通路。 （第13题图）解：见上右图。14.在完全图Kn中，（1）任意两点间有多少条边？ （2）有多少个圈？ （3）包含某条边e的圈有多少个？解：（1）任意两点间有1条边；（2）有个圈；（3）包含某条边e的圈有个。15. 若图G=<V,E>中存在一条包含G的所有顶点的通路，则此通路称为哈密尔顿通路。如存在一个包含G的所有顶点的圈，则这个圈为G的哈密尔顿圈。图G就称为哈密尔顿图。证明：完全图是哈密尔顿图。证明：因为完全图可以找到一条通路通过所有顶点。16.某人从A出发到B，C，D，E四地去旅游，在回到A，各地间的路程如下图： 第16题问应如何选择旅游路线，使总路程最短？解：ABEDCA 即 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 问应怎样安排加工任务，使每个工人加工一种零件，一个零件由一个工人加工，且使工人们的总收益最大？解：所以最大收益值为5+10+7+5=27