图论

图论

内容提要

第一章 图的基本概念

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

第二章 图的连通性

割点、割边和块；边连通与点连通；连通度；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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库图论在线全文阅读。