5学习指导与习题解答-4

《5学习指导与习题解答-4》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章图与网络§4.1基本要求1.掌握图、有限图、母图、子图、支撑子图、完全图、补图等概念，了解有限图中点的度的性质，掌握图的矩阵表示：关联矩阵、邻接矩阵。2.掌握路、简单路、回路、连通图等概念。3.理解Dijkstra算法，并能够在已知权图中使用该算法求出任意两点间的最短路。4.掌握树、支撑树的概念以及图是树的几个等价命题。5.理解Kruskal算法，并能够应用它求已知加权连通图的最优树。了解求最优树的Prim算法，会总结Sollin算法。6.掌握有向图、有向子图、有向路、简单有向路、有向回路等

2、概念。7.掌握有向图的强连通性和有向图的根的概念，了解二者的关系。8.掌握有向树的概念以及有向树与树的转化定理。9.掌握Euler路、Euler图的概念，掌握有向图中和无向图中Euler图的充要条件，并能利用判断某图是否为Euler图。了解从Euler路得出有向支撑树以及从有向支撑树得出Euler路的方法。10.掌握Hamilton路、Hamilton回路、Hamilton图的概念以及Hamilton图的必要条件和若干充分条件。11.了解流动推销员问题和求解Hamilton路的逼近算法。12.掌握

3、平面图、平面图的对偶图、柏拉图体等概念，掌握平面图的库拉托夫斯基判定准则、平面图的Euler公式以及平面图的性质。了解平面图的着色问题。13.掌握匹配、极大匹配、最大匹配、完全匹配、M-交错路、M-交回错路、M-增广路等概念。会求一个图中的最大匹配，和判定一个匹配是否为最大匹配（完全匹配）。14.掌握二部图等概念，掌握判定一个二部图中存在完备匹配的充要条件以及在二部图G=(P1,L,P2)中，寻找P1到P2的一个完备匹配的Hungarian算法。15.了解Konig无限性引理以及王浩定理。91§4

4、.2主要解题方法教材中本章讲得比较详细，有些解题方法已给出，比如，如何应用Dijkstra算法、Kruscal算法，判断某个图是Euler图所需的Euler图的充要条件等等，在这里就不再赘述。4.2.1关于图中点的度的问题这类题目的解题思路比较清晰。主要用到的知识点是：（1）点的度、图的边数、点数之间的数量关系。在有限图G＝（P，L）中有：=2m。其中m为图G的边数

5、L(G)

6、。（2）由于教材中定义的图（有的图论书籍中称之为简单图）中不允许有反身边和平行边，所以若图的点的个数

7、P(G)

8、为n，则图

9、中每个点的度的取值于集合{0，1，…，n-1}。例4.2.1试证明：在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。证明：把每个人对应成相应的顶点，两个人具有朋友关系当且仅当相应的顶点相邻。显然，这是简单图，设为G。所以，原命题等价于证明在该图中一定存在两个点的度相等。使用反证法。假设该图中任何一对顶点的度都不相等。设G的顶点数为n，则由图中任何一对顶点的度都不相等知，n个顶点的度数序列只可能为：0，1，…，n-1。现在我们从图G中删去度为0的点，得到G’，G’点数是n-1，并且存

10、在度为n-1的点，因此，G’不是简单图，因为若是简单图，点数n-1，每个点的度的取值于集合{0，1，…，n-2}，不会存在度为n-1的点。所以，G也不是简单图，产生矛盾。故原假设不对，在该图中一定存在两个点的度相等。因此，在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。例4.2.2设图G中各点的度都是3，且点数n与边数m间有如下关系：2n-3=m。问：G中点数n和边数m各为多少？解：由图G中各点的度都是3知，=3n，而=2m，故，3n=2m。再由已知2n-3=m，解得n=6，m=9

11、。例4.2.391给完全图的每条边加上方向，构成有向完全图。证明：在任何有向完全图中，所有点输入次数的平方和等于所有点输出次数的平方之和。证明：假设有向完全图G有n个点，m个弧。对任意点vi，如果用dG-(vi)和dG+(vi)分别表示vi的输入次数和输出次数，则由有向完全图是给完全图的每条边加上方向构成的，以及完全图的特点(每一点与所有其它点都相邻)知，dG-(vi)+dG+(vi)=n-1，m=。又因=2m，所以，=n(n-1)，==。故==。===。例4.2.4完全图Kn是几笔画图？说明理由

12、。解：当n=1时，Kn为平凡图。当n≠1且为奇数时，对Kn中任一点u，dG(u)=n-1为偶数，所以Kn为Euler图，可一笔画出。当n≠1且为偶数时，对Kn中任一点u，dG(u)=n-1为奇数，故Kn中有n/2对奇数度的点，因此可n/2笔画出。4.2.2关于连通图的问题证明一个图是连通图一般有两种方法：91方法一.直接证明。取图中任意两个点u，v，证明都存在从u到v的路。使用这种方法往往要按照所取点的相对位置分类讨论，注意考虑清楚各种情况，不要遗漏。参见例4.2.5。方法二.使用