第四章 图与网络
§4.1 基本要求
1. 掌握图、有限图、母图、子图、支撑子图、完全图、补图等概念，了解有限图中点的度
的性质，掌握图的矩阵表示：关联矩阵、邻接矩阵。 2. 掌握路、简单路、回路、连通图等概念。
3. 理解Dijkstra算法，并能够在已知权图中使用该算法求出任意两点间的最短路。 4. 掌握树、支撑树的概念以及图是树的几个等价命题。
5. 理解Kruskal算法，并能够应用它求已知加权连通图的最优树。了解求最优树的Prim算
法，会总结Sollin算法。
6. 掌握有向图、有向子图、有向路、简单有向路、有向回路等概念。 7. 掌握有向图的强连通性和有向图的根的概念，了解二者的关系。 8. 掌握有向树的概念以及有向树与树的转化定理。
9. 掌握Euler路、Euler图的概念，掌握有向图中和无向图中Euler图的充要条件，并能利
用判断某图是否为Euler图。了解从Euler路得出有向支撑树以及从有向支撑树得出 Euler路的方法。
10. 掌握Hamilton路、Hamilton回路、Hamilton图的概念以及Hamilton图的必要条件和若
干充分条件。
11. 了解流动推销员问题和求解Hamilton路的逼近算法。 12. 掌握平面图、平面图的对偶图、柏拉图体等概念，掌握平面图的库拉托夫斯基判定准则、
平面图的Euler公式以及平面图的性质。了解平面图的着色问题。
13. 掌握匹配、极大匹配、最大匹配、完全匹配、M-交错路、M-交回错路、M-增广路等概
念。会求一个图中的最大匹配，和判定一个匹配是否为最大匹配（完全匹配）。
14. 掌握二部图等概念，掌握判定一个二部图中存在完备匹配的充要条件以及在二部图
G=(P1, L, P2)中，寻找P1到P2的一个完备匹配的Hungarian算法。 15. 了解Konig无限性引理以及王浩定理。
60
§4.2 主要解题方法
教材中本章讲得比较详细，有些解题方法已给出，比如，如何应用Dijkstra算法、Kruscal算法，判断某个图是Euler图所需的Euler图的充要条件等等，在这里就不再赘述。
4.2.1 关于图中点的度的问题
这类题目的解题思路比较清晰。主要用到的知识点是：
（1）点的度、图的边数、点数之间的数量关系。在有限图G＝（P，L）中有：
v?P(G)?dG(v)=2m。
其中m为图G的边数|L(G)|。
（2）由于教材中定义的图（有的图论书籍中称之为简单图）中不允许有反身边和平行边，所以若图的点的个数|P(G)|为n，则图中每个点的度的取值于集合{0，1，…，n-1}。
例4.2.1 试证明：在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。
证明：把每个人对应成相应的顶点，两个人具有朋友关系当且仅当相应的顶点相邻。显然，这是简单图，设为G。所以，原命题等价于证明在该图中一定存在两个点的度相等。
使用反证法。假设该图中任何一对顶点的度都不相等。设G的顶点数为n，则由图中任何一对顶点的度都不相等知，n个顶点的度数序列只可能为：0，1，…，n-1。
现在我们从图G中删去度为0的点，得到G’， G’点数是n-1，并且存在度为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知，
v?P(G)?dGG(v)=3n，
而
v?P(G)?d(v)=2m，故，
3n=2m。
再由已知2n-3=m，解得
n=6，m=9。
例4.2.3 给完全图的每条边加上方向，构成有向完全图。证明：在任何有向完全图中，
61
所有点输入次数的平方和等于所有点输出次数的平方之和。
证明：假设有向完全图G有n个点，m个弧。对任意点vi，如果用dG-(vi)和dG+(vi)分别表示vi的输入次数和输出次数，则由有向完全图是给完全图的每条边加上方向构成的，以及完全图的特点(每一点与所有其它点都相邻)知，
dG-(vi)+dG+(vi) = n-1，
m=
又因
v?P(G)1n(n?1)。 2G?d(v)=2m，
所以，
?[di?1n?nG(vi)]=n(n-1)，
1?n(n?1)。 ==[d(v)][d(v)]??GiGi2i?1i?1故
n?[dG(vi)]=?[(n?1)?dG(vi)]2
?2?i?1i?1nn=
?[(n?1)i?1nn2?2(n?1)dG(vi)?dG(vi)2]。
nn?? =
?(n?1)?2(n?1)?dG(vi)??[dG(vi)]2
2??i?1i?1i?12n1?2 = n(n?1)?2(n?1)n(n?1)??[dG(vi)]
2i?1n =
?[di?1?G(vi)]2。
例4.2.4 完全图Kn是几笔画图？说明理由。
解：当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 关于连通图的问题
证明一个图是连通图一般有两种方法：
62
方法一. 直接证明。取图中任意两个点u，v，证明都存在从u到v的路。 使用这种方法往往要按照所取点的相对位置分类讨论，注意考虑清楚各种情况，不要遗漏。参见例4.2.5。
方法二. 使用反证法。首先假设图不连通，则它具有m个分支，其中m≥2，然后根据题目条件推出矛盾。推矛盾的过程，通常是将具有m个连通分支的图的边数放到最大的过程，使每个连通分支都是完全图。为了简化证明，有些题目可以假设图至少有两个连通分支就行了，比如，习题4.1的第5题就是采用此证法。
例4.2.5 若图G是不连通的，试证G的补图G’是连通的。
证明：由图G是不连通的，可设图G的连通分支为：G1，G2，…，Gk，k≥2。由补图的定义知，任意两个连通分支间的所有连线都是图G的补图G’中的边。
任取G中两个点u和v，有如下两种情况：
（1）u和v分别属于G的两个不同的连通分支，则uv是G’中的边，因此，G’中存在点u到点v的路（u，v）。
（2）u和v属于同一个连通分支，则在另一个连通分支中取点w，于是，uw和vw都是G’中的边。故G’中存在点u到点v的路（u，w，v）。
综上，G’是连通的。
例4.2.6 设G＝（P，L）是连通图，但不是完全图，则存在三个点u、v和w?P(G)，使得uv，vw?L(G)，但uw?L(G)。
证明：反证法，假设不存在满足题中结论要求的点，即，对任意三个点u、v和w?P(G)，若uv，vw?L(G)，则一定也有uw?L(G)。这样，对于图G中的任意点u，都有如下结论：
u与所有与u相邻的点的相邻点都相邻。
这就是说，在这样的图中，该相邻关系具有传递性，所以可以得到：
u和v相邻当且仅当u和v相连。
而G是连通图，u与所有其它点都相连，因此，u与所有其它点都相邻。再由u的任意性知，G是一个完全图。
4.2.3 关于补图的问题
例4.2.7 一个图如果同构于它的补图，则称该图为自补图。 （1）试给出一个5个点的自补图。
（2）证明：一个图是自补图，其对应的完全图的边数必是偶数。 （3）是否有3个点或6个点的自补图？ 解： （1）
图4.2.1
63
（2）设G是自补图，且有m条边，则由于它同构于它的补图，所以它的补图的边数也是m，因此，G对应的完全图的边数为2m，即为偶数。
22（3）3个点的完全图的边数为C3=3，6个点的完全图的边数为C6=15，均为奇数。由
（2）的结论知，不存在3个点或6个点的自补图。
例4.2.8 试证明：对于任何一个具有6个点的图，要么它包含一个三角形，要么它的补图包含一个三角形（即，对于任何一个具有6个点的图，该图或它的补图中存在3个结点彼此相邻）。
证明：设G为具有6个点的图，G的补图为G’。考察G中的任意一个点a，由补图的定义知，另外5个点要么在G中与a相邻，要么在G’中与a相邻。这样，我们就将这5个点分成两类，把在G中与a相邻的点归成一类，在G’中与a相邻的点归成另一类。那么，必有一类至少含有三个点，不妨设其中的三个点为b，c，d，如图4.2.2所示。
a b d
c 图4.2.2
显然，该图必然是G’’的子图，这里的G’’或者是G，或者是G’。
（1）如果边bc，cd，bd中有一条在G’’中，不妨设为bc，则在G’’中包含以a，b，c为顶点的三角形。
（2）否则，如果边bc，cd，bd都不在G’’中，那么都一定在G’’的补图中，因此，G’’的补图中包含以b，c，d为顶点的三角形，而G’’的补图也或者是G，或者是G’。
综上，要么G包含一个三角形，要么它的补图包含一个三角形。
例4.2.8其实是组合数学中抽屉原理的一个推广，被称为Ramsey定理。我们在这里不对该定理进行讨论，只是就题论题。在该例证明中我们引入了将图中的点按某一标准分类讨论的思想，希望读者注意理解和掌握。
例4.2.9 设G＝（P，L）是图，| P (G)|=n，为奇数，问：G与G的补图G’的奇数点的个数有什么关系？
解：因为G∪G’是完全图Kn，因为n为奇数，所以Kn中每个点的度k-1为偶数。因此，若在G中有一个奇数度的点u，则u在G’中也必为奇数度点，反之亦然。
故G与G的补图G’的奇数点的个数相同。
4.2.4 判断Hamilton图的问题
判断某图不是Hamilton图，要利用Hamilton图的必要条件。如，教材中由定理4.4.1知，图4.4.2不是Hamilton图。
64