图论

图论

内容提要

第一章 图的基本概念

图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。 路、圈与连通图；最短路问题。 树及其基本性质；生成树；最小生成树。

第二章 图的连通性

割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。

第三章 匹配问题

匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。

第四章 欧拉图与哈密尔顿图

欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。

第五章 支配集、独立集、覆盖集与团

支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。

第六章 图的着色问题

点着色；边着色；平面图；四色猜想；色多项式；色数的应用。

第七章 网络流理论

有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费用流问题；最小费用最大流；网络流理论的应用。

主要参考书

[1] J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中译本（吴望名等译）。 [2] B.Bollobas, Modern graph theory (现代图论)，科学出版社，2001。 [3] 蒋长浩，图论与网络流，中国林业出版社，2001。 [4] 田丰，马仲蕃，图与网络流理论，科学出版社，1987。

[5] 徐俊明，图论及其应用，中国科技大学出版社，1998。 [6] 王树禾，图论及其算法，中国科技大学出版社，1994。 [7] 殷剑宏，吴开亚，图论及其算法，中国科技大学出版社，2003。

1

第一章 图的基本概念

§1.1 图的基本概念

1. 图(graph)：一集元素及它们之间的某种关系。具体地说，图是一个二元组(V,E)，其中集合V称为顶点集，集合E是V?V的一个子集（无序对，元素可重复），称为边集。 例1.1.1 G?(V,E)，其中

V?{v1,v2,v3,v4,v5}，E?{(v1,v2),(v2,v3),(v3,v4),(v3,v5),(v1,v5),(v1,v5),(v5,v5)}。这便定义出一个图。

2. 图的图示

通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。这样画出的平面图形称为图的图示。

例如，例1.1.1中图的一个图示为 v1 e1 e6 v2 e5

e4 e7 e2 v5 v3 e3 v4 注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。比如下图是例1.1中图的另一个图示：

v1 e

e5 v4 e1 v5

e4 e7 e3

v2 e2 v3

（2）图的图示直观易懂，因此以后一般说到一个图，我们总是画出它的一个图示来表示。 3. 一些概念和术语

（1） 点与边的关联(incident) （2） 点与点的相邻（adjacent） （3） 边与边的相邻

（4） 边的端点（end vertices） （5） 环边(loop) （6） 重边(multiedge) （7） 简单图(simple graph)

6 2

（8） 完全图(complete graph)

（9） 图的顶点数（图的阶）?、边数?

（10） 顶点v的度(degree)：d(v) = 顶点v所关联的边的数目（环边计两次）。 （11） 图G的最大度：?(G)?max{dG(v)|v?V(G)}

图G的最小度：?(G)?min{dG(v)|v?V(G)}

（12）正则图(regular graph)：每个顶点的度都相等的图。

（13）图的补图(complement)：设G是一个图，以V(G)为顶点集，以{(x,y)|(x,y)?E(G)}为边集的图称为G的补图，记为G。

定理1.1.1

v?V(G)?d(v)?2?

证明：按每个顶点的度来计数边，每条边恰数了两次。 推论1.1.1 任何图中，奇度顶点的个数总是偶数（包括0）。 4. 子图

子图(subgraph)：如果V(H)?V(G)且E(H)?E(G)，则称图H是G的子图，记为

H?G。

生成子图(spanning subgraph): 若H是G的子图且V(H)?V(G)，则称H是G的生成子图。 点导出子图(induced subgraph)：设V??V(G)，以V?为顶点集，以两端点均在V?中的边的全体为边集所组成的子图，称为G的由顶点集V?导出的子图，简称为G的点导出子图，记为G[V?].

边导出子图(edge-induced subgraph)：设E??E(G)，以E?为边集，以两端点均在E?中的边的全体为点集所组成的子图，称为G的由边集E?导出的子图，简称为G的边导出子图，记为G[E?]. 5. 路和圈

途径(walk)：图G中一个点边交替出现的序列w?vi0ei1vi1ei2?eikvik。 迹(trail)：边不重的途径。 路(path): 顶点不重复的迹。

（注：简单图中的路可以完全用顶点来表示，P?vi0vi1?vik） 闭途径（closed walk）：起点和终点相同的途径。

闭迹(closed trail)：起点和终点相同的迹，也称为回路（circuit）。 圈(cycle): 起点和终点相同的路。

3

注：

（1）途径（闭途径）、迹（闭迹）、路（圈）上所含的边的个数称为它的长度。 （2）简单图G中长度为奇数和偶数的圈分别称为奇圈(odd cycle)和偶圈(even cycle)。 （3）对任意x,y?V(G)，从x到y的具有最小长度的路称为x到y的最短路（shortest path），其长度称为x到y的距离(distance)，记为dG(x,y)。

（4）图G的直径(diameter): D?max{dG(x,y)|?x,y?V(G)}.

（5）简单图G中最短圈的长度称为图G的围长(girth)，最长圈的长度称为图G的周长(circumference)。

例1.1.2 设G是一个简单图，若?(G)?2，则G中必含有圈。

证明：设G中的最长路为P?v0v1?vk。因d(v0)?2，故存在与v1相异的顶点v与v0相邻。若v?P，则得到比P更长的路，这与P的取法矛盾。因此必定v?P，从而G中有圈。证毕。

例1.1.3 设G是简单图，若?(G)?3,则G必有偶圈。 证明：设P?v0v1?vk是G的最长路。

因为d(v0)?3， 所以存在两个与v1相异的顶点v?,v??与v0相邻。v?,v??必都在路P上，否则会得到比P更长的路。无妨设v??vi,v???vj,(i?j)。

若i,j中有奇数，比如i是奇数，则路P上v0到vi的一段与边v0vi构成一个偶圈； 若i,j都是偶数，则路P上vi到vj的一段与边v0vi及v0vj构成一个偶圈。证毕。 例1.1.4 设G是简单图，若?(G)?3,则G中各个圈长的最大公因数是1或2。

证明：由上例知，G中有长分别为i?1,j?1和j?i?2的圈。若i?1,j?1，j?i?2三数有公因数m?2，则m|(j?i)，于是m|2，这是不可能的。因此i?1,j?1，j?i?2三数的公因数必不超过2。从而各个圈长的最大公因数是1或2。证毕。 6. 二部图

二部图 (bipartite graph)：若图G的顶点集可划分为两个非空子集X和Y，使得任一条边都有一个端点在X中，另一个端点在Y中，则称G为二部图（或偶图），记为G＝(X?Y,E)，

(X,Y)称为G的一个划分。

完全二部图(complete bipartite graph)：在二部图G?(X?Y,E)中，若X的每个顶点与Y的每个顶点有边连接，则称G为完全二部图；若|X|?m，|Y|?n，则记此完全二部图为

Km,n。

4

定理1.1.2一个图是二部图当且仅当它不含奇圈。

证明： 必要性：设C?v0v1?vkv0是二部图G?(X?Y,E)的一个圈。无妨设v0?X，由二部图的定义知，v1?Y，v2?X，?，一般地，v2i?X，v2i?1?Y，（i?0,1,?）。又因v0?X，故vk?Y，因而k是奇数。注意到圈C上共有k?1条边，因此是偶圈。 充分性：设G不含奇圈。取u?V(G)，令

X?{v?V(G)|d(u,v)＝odd}，Y?{v?V(G)|d(u,v)＝even}。

任取一条边e?v1v2，欲证v1,v2分属于X和Y。设P，Q分别是u到v1,v2的最短路。 （1）如果P?Q?v2v1或Q?P?v1v2，则v1,v2到u的距离奇偶性相反，v1,v2分属于X和Y。

（2）否则，设u?是P与Q的最后一个公共顶点，因P的(u,u?)段和Q的(u,u?)段都是u到u?的最短路，故这两段长度相等。

假如P，Q的奇偶性相同，则P的(u?,v1)段和Q的(u?,v2)段奇偶性相同，这两段与边e构成一个奇圈，与定理条件矛盾。可见P，Q的奇偶性不同，从而v1,v2分属于X和Y。

这便证明了G是一个二部图。 证毕。 7. 连通性

图中两点的连通：如果在图G中u，v两点有路相通，则称顶点u，v在图G中连通。 连通图（connected graph）：图G中任二顶点都连通。

图的连通分支（connected branch, component）：若图G的顶点集V(G)可划分为若干非空子集

V1,V2,?,V?，使得两顶点属于同一子集当且仅当它们在G中连通，则称每个子图G[Vi]为

图G的一个连通分支（i?1,2,?,?）。

注：（1）图G的连通分支是G的一个极大连通子图。 （2）图G连通当且仅当?＝1。

例1.1.5设有2n个电话交换台，每个台与至少n个台有直通线路，则该交换系统中任二台均可实现通话。

证明：构造图G如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线路。问题化为：已知图G有2n个顶点，且?(G)?n，求证G连通。

事实上，假如G不连通，则至少有一个连通分支的顶点数不超过n。在此连通分支中，顶点的度至多是n?1。这与?(G)?n矛盾。证毕。 例1.1.6若图中只有两个奇度顶点，则它们必连通。

证明：用反证法。假如u与v不连通，则它们必分属于不同的连通分支。将每个分支看成一个图时，其中只有一个奇度顶点。这与推论1.1.1矛盾。证毕。

5

§1.4 生成树与最小生成树

一、生成树（spanning tree）

定义1.4.1 设T是图G的一个子图，如果T是一棵树，且?(T)??(G)，则称T是G的一个生成树。

定理1.4.1 每个连通图都有生成树。

证明：设G是一个连通图。令A?{G?|G?是G的连通子图且?(G?)??(G)}。易见A非空。从A中取边数最少的一个，记为T。下证T是G的生成树。显然只需证明T是树即可。

事实上，已知T连通，下证T无圈。

若T有圈C，则去掉C上任一条边e，T?e仍连通。从而T?e?A。但T?e比T少一条边，这与T的取法矛盾。证毕。 推论1.4.1 若G连通，则????1。

证明：取G的生成树T，则?(G)??(T)??(T)?1??(G)?1。证毕。

二、最小生成树问题

问题描述：在赋权图G中，求权最小的生成树。即：求G的一棵生成树T，使得

w(T)?min?w(e)。

Te?T算法： 1. Kruskal算法

step1. take e1?E(G)such that w(e)?min{w(e)},i:?1.

e?GStep2. find ei?1?E(G)\\{e1,e2,?,ei}such that (1) G[{e1,e2,?,ei,ei?1}] does not contain any cycle, and (2) ei?1 is the one with minimum weight that meet (1). Step3. if i+1 =?(G)?1, stop; else, i:?i?1, go to step2.

定理1.4.2 设e1,e2,?,e?(G)?1是Kruskal算法获得的边，则边导出子图G[{e1,e2,?,e?(G)?1}]是G的最小生成树。

证明：记T? G[{e1,e2,?,e?(G)?1}]。显然T无圈，因此T是森林。设它有w个连通分支，则?(T*)??(T*)?w??(T*)?1?(?(G)?1)?1??(G)。但T是G的子图，故?(T)??(G)，于是

11

*

**

*

*?(T*)??(G)?1??(T*)?1。

由定理1.3.1的（3），T是一棵树，从而是G的一棵生成树。

下证其最优性，用反证法。

假设T不是权最小的生成树（下称最优树）。

对G的任一棵生成树T，记f(T)?min{i|ei?{e1,e2,?,e??1}且ei?T}。选取一棵使f(T)最大的最优树，记为T。（T不会是T）。设f(T)?k。由f(T)的定义，

*

*

~~*

~~~~~e1,e2,?,ek?1既在T*上也在T上，但ek不在T上。因此T?ek含有一个圈C。C上必有一

~~?也是一棵生成树，?)。??T*。条边ek显然T??(T?ek)?ek且w(T?)?w(T)?w(ek)?w(ek

按照算法，ek是使G[{e1,e2,?,ek}]中无圈的边中权最小的。注意

?}] 是T的子图，也无圈。故由算法规则知：w(ek?)?w(ek)。由前式，G[{e1,e2,?,ek?1,ek~~??Tw(T?)?w(T)，f(T)?k?f(T)（注意由于e1,e2,?,ek?1在T*这说明也是最优树，但

~??T*，故ek??{e1,e2,?,ek?1}）T上且ek。这与的取法矛盾。证毕。

例1.4.1 欲建设一个连接5个城市的光纤通信网络。各城市间线路的造价如图所示，求一个使总造价最少的线路建设方案。

2. Prim算法

3 6 ~v1 8.5 10v5 11 12 14 6.4 8 v2 5 v3 v4 step1. 任取v0?V(G)，令S0?{v0}，S0?V(G)\\S0，i:?0。

step2. 求Si到Si间权最小的边ei，设ei的属于Si的端点为vi，令Si?1:?Si?{vi}，

Si?1?V(G)\\Si?1。

Step3. 若i???1，停止；否则，令i:?i?1，继续step2。

12

习题一

1． 证明：??2????。

2． 如果??2,???，则连通图G至少有两个1度顶点。 3． 如果????1，则存在v?V(G)使得d(v)?3。 4． 在k度正则图G中，k??0(mod2)。

5． 晚会上大家握手言欢。证明：握过奇数次手的人必有偶数个。

6． n个运动队进行一项竞赛。已赛完n?1局。试证一定存在一个队至少参加过3局比赛。

习题二 1． 证明：若G是完全二部图，则???24。

2． 证明：若G?(X?Y,E)是一个k度正则二部图，则|X|?|Y|。 3． 若G是简单图且?(G)?k，则G有长为k的路。 4． 证明连通图中两条最长路必有公共顶点。

5． 设G是直径为2的简单图，且?(G)???2，则??2??4。 6． ??2的简单图必含有长至少为??1的圈。 7． 若???，则G中必有圈。

习题三

1． 不含圈的图称为森林（forest），证明：

（1） G是森林当且仅当????w；（2）无孤立点的森林至少有2w个1度顶点。 这里w表示G的连通分支数，孤立点指零度顶点。

2． 证明非平凡树中最长路的起点和终点都是叶子（1度点）。 3． 恰有两个叶子的树必是路。

4． 若G是树且??k，则G至少有k个1度顶点。 5． 证明每个树都是二部图。 6． 修改Kruskal算法用以：

（1）求赋权连通图中的最大权生成树；（2）求不连通赋权图中的最小权生成林。

13

课外阅读：

[1] 阅读参考书上有关内容。

[2] D. Jungnickel, Graphs, Networks and Algorithms, (Algorithms and Computation in Mathematics, Vol.5), Springer, 1998, 第3章、第4章。

[3] N.Deo and N.Kumar, Computation of Constrained Spanning Trees: A Unified Approach, in Network Optimization (P.M. Pardalos, D.W. Hearn and W.W. Hager editors.), Lecture Notes in Economics and Mathematical Systems 450, Springer-Verlag, 1997.

[4] M.R. Henzinger and V. King, Maintaining minimum spanning forests in dynamic graphs, SIAM J. Computing, 31:2(2001), pp364-374.

[5] Guoliang Xue and Shangzhi Sun, Optimal multicast tree in communication systems with channel capacities and channel reliabilities, IEEE Transactions on Communications, 47:5(1999), pp662-663.

14

第二章 图的连通性

连通图：任二顶点间有路相连。 例

可见在连通图中，连通的程度也是有高有低。

本章的目的就是定义一种参数来度量连通图连通程度的高低。

§2.1 割边、割点与连通度

一、割点：

定义2.1.1 设v?V(G)，如果w(G?v)?w(G)，则称v为G的一个割点。（该定义与某些著作有所不同，主要是在有环边的顶点是否算作割点上有区别）。

例

定理2.1.1 如果点v是图G的一个割点，则边集E(G)可划分为两个非空子集E1和E2，使得

G[E1]和G[E2]恰好有一个公共顶点v。

推论2.1.1 对连通图G，顶点v是G的割点当且仅当G?v不连通。

以上两个结论的证明留作习题。

定理2.1.2 设v是树T的顶点，则v是T的割点当且仅当d(v)?1。 证明：必要性：设v是T的割点，下面用反证法证明d(v)?1。 若d(v)?0，则T?K1，显然v不是割点。

若d(v)?1，则T?v是有?(T?v)?1条边的无圈图，故是树。从而w(T?v)?1?w(T)。因此v不是割点。

以上均与条件矛盾。

充分性：设d(v)?1，则v至少有两个邻点u,w。路uvw是T中一条(u,w)路。因T是树，uvw是T中唯一的(u,w)路，从而w(T?v)?1?w(T)。故v是割点。证毕。 推论2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。

证明：设T是G的生成树，则T至少有两个叶子u,v，由上一定理知，u,v都不是T的割点，

15

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