图论讲义第1章-图的概念
图论与网络流理论
（Graph Theory and Network Flow Theory）
高随祥
中科院研究生院专业基础课
学时/学分：60/3
本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数理统计各专业的硕士学位研究生作为专业基础课，也可供物理学、化学、天文学、地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、信号等学科专业的硕士研究生选修。主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用。为学习者将来从事有关方面的理论研究打下基础，也为进行应用性研究提供一种有力的工具。
内容提要
第一章 图的基本概念
图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。
路、圈与连通图；最短路问题。
树及其基本性质；生成树；最小生成树。
第二章 图的连通性
割点、割边和块；边连通与点连通；连通度；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. 图(graph)：一集元素及它们之间的某种关系。具体地说，图是一个二元组),(E V ，其中集合V 称为顶点集，集合E 是V 中元素组成的某些无序对的集合，称为边集。 例1.1.1 ),(E V G =，其中
},,,,{54321v v v v v V =，)},(),,(),,(),,(),,(),,(),,{(55515153433221v v v v v v v v v v v v v v E =。
这便定义出一个图。
图的顶点集中的元素称为顶点，边集中的元素称为边。在本书中边e = (u , v ) 也常写为e = uv ，顶点u 和v 称为边e 的端点，反过来也称边e 连接顶点u 和v 。图G 的顶点数目||V 称为图G 的阶，边的数目||E 称为图G 的边数。本书中一般将图的边数记为ε，将图的阶记为υ。
2. 图的图示
通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。这样画出的平面图形称为图的图示。
例如，例1.1.1中图的一个图示为
注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。比如下图是例1.1.1中图的另一个图示：
（2）图的图示直观易懂，因此以后一般说到一个图，我们总是画出它的一个图示来表示。 3. 一些术语和概念
设G = (V , E)是一个图，下述概念中顶点均取自V ，边均取自E 。
（1） 点与边的关联(incident)：如果在图G 中点v 是边e 的一个端点，则称点v 与边e 在
图G 中相关联。 （2） 点与点的相邻(adjacent)：如果图上两点u ,v 被同一条边相连，则称u ,v 在图G 中相
邻。
（3） 边与边的相邻：如果图G 中两条边有至少一个公共端点，则称这两条边在图G 中相
邻。 （4） 环边(loop)：图中两端点重合的边称为环边。
（5） 重边(multiedge)：设u 和v 是图G 的顶点，图G 中连接u 和v 的两条或两条以上的
边称为图G 中u 、v 间的重边。 （6） 简单图(simple graph)：既无环边也无重边的图称为简单图。
（7） 完全图(complete graph)：任意两点间都有一条边的简单图称为完全图，n 阶完全图记
为K n . （8） 平凡图(trivial graph): 只有一个顶点，没有边的图。 （9） 空图(empty graph): 边集为空的图。 （10） 零图(null graph): 顶点集为空的图。
（11） 顶点v 的度(degree)：图G 中顶点v 所关联的边的数目（环边计两次）称为顶点v 的
度，记为d G (v )或d (v )。 （12） 图G 的最大度：)}(|)(max{)(G V v v d G G ∈=Δ；
图G 的最小度：)}(|)(min{)(G V v v d G G ∈=δ。
（13）正则图(regular graph)：每个顶点的度都相等的图。
（14）图的补图(complement)：设G 是一个图，以)(G V 为顶点集，以)}(),(|),{(G E y x y x ?为边集的图称为G 的补图，记为G 。 定理1.1.1 对任何图G ，都有
()
()2v V G d v ε∈=∑
。
证明：按每个顶点的度来计数边，每条边恰数了两次。 推论1.1.1 任何图中，奇度顶点的个数总是偶数（包括0）。 证明留作练习。 4. 子图
子图(subgraph)：对图G 和H ，如果)()(G V H V ?且)()(G E H E ?，则称图H 是图G 的子图，记为G H ?。
生成子图(spanning subgraph): 若H 是G 的子图且()()V H V G =，则称H 是G 的生成子图。 点导出子图(induced subgraph)：设G 是一个图，)(G V V ?′。以V ′为顶点集，以G 中两端点均属于V ′的所有边作为边集所组成的子图，称为G 的由顶点集V ′导出的子图，简称为G 的点导出子图，记为][V G ′.
边导出子图(edge-induced subgraph)：设G 是一个图，)(G E E ?′。以E ′为边集，以E ′中边的所有端点作为顶点集所组成的子图，称为G 的由边集E ′导出的子图，简称为G 的边导出子图，记为][E G ′。
设)(G V V ?′，)(G E E ?′，今后经常用G V ′?表示从图G 中删除顶点子集V ′（连同它们关联的边一起删去）所获得的子图，用G E ′?表示从图G 中删除边子集E ′（但不删除它们的端点）所获得的子图。特别地，对顶点v 和边e ，常用G v ?表示G {}v ?，G e ?表示{}G e ?图G 的一个顶点子集E ′。 5. 路和圈
途径(walk)：图G 中一个点边交替出现的序列k k i i i i i i v e e v e v w 2110=称为图G 的一条途径，其中0i v 、k i v 分别称为途径w 的起点和终点，w 上其余顶点称为中途点。 迹(trail)：图G 中边不重复的途径称为迹。 路(path)：图G 中顶点不重复的迹称为路。
（注：简单图中的路可以完全用顶点来表示，k i i i v v v P 10=） 闭途径(closed walk)：图G 中起点和终点相同的途径称为闭途径。
闭迹(closed trail)：图G 中边不重复的闭途径称为闭迹，也称为回路（circuit ）。 圈(cycle)：中途点不重复的闭迹称为圈。
注：
（1）途径（闭途径）、迹（闭迹）、路（圈）上所含的边的数目称为它的长度。 （2）简单图G 中长度为奇数和偶数的圈分别称为奇圈(odd cycle)和偶圈(even cycle)。 （3）对任意)(,G V y x ∈，从x 到y 的具有最小长度的路称为x 到y 的最短路（shortest path ），其长度称为x 到y 的距离(distance)，记为),(y x d G 。
（4）简单图G 中最短圈的长度称为图G 的围长(girth)，最长圈的长度称为图G 的周长(circumference)。
例1.1.2设G 是一个简单图，若2)(≥G δ，则G 中必含有圈。
证明：设G 中的最长路为k v v v P 10=。因2)(0≥v d ，故存在与1v 相异的顶点v 与0v 相邻。若P v ?，则得到比P 更长的路，这与P 的取法矛盾。因此必定P v ∈，从而G 中有圈。证毕。
例1.1.3 设G 是简单图，若3)(≥G δ,则G 必有偶圈。 证明：设k v v v P 10=是G 的最长路。
因为3)(0≥v d ， 所以存在两个与1v 相异的顶点v v ′′′,与0v 相邻。v v ′′′,必都在路P 上，否则会得到比P 更长的路。无妨设)(,,j i v v v v j i <=′′=′。
若j i ,中有奇数，比如i 是奇数，则路P 上0v 到i v 的一段与边i v v 0构成一个偶圈； 若j i ,都是偶数，则路P 上i v 到j v 的一段与边i v v 0及j v v 0构成一个偶圈。证毕。 例1.1.4设G 是简单图，若3)(≥G δ,则G 中各个圈长的最大公因数是1或2。
证明：由上例知，G 中有长分别为1,1++j i 和2+?i j 的圈。若1,1++j i ，2+?i j 三数有公因数2>m ，则|()m j i ?，于是2|m ，这是不可能的。因此1,1++j i ，2+?i j 三数的公因数必不超过2。从而各个圈长的最大公因数是1或2。证毕。 6. 二部图
二部图 (bipartite graph)：若图G 的顶点集可划分为两个非空子集X 和Y ，使得G 的任一条边都有一个端点在X 中，另一个端点在Y 中，则称G 为二部图（或偶图），记为G ＝
),(E Y X ∪，),(Y X 称为G 的一个顶点二划分。
完全二部图(complete bipartite graph)：在二部图),(E Y X G ∪=中，若X 的每个顶点与Y 的每个顶点有边连接，则称G 为完全二部图；若m X =||，n Y =||，则记此完全二部图为
n m K ,。
定理1.1.2一个图是二部图当且仅当它不含奇圈。
证明： 必要性：设010v v v v C k =是二部图),(E Y X G ∪=的一个圈。无妨设X v ∈0，由二部图的定义知，Y v ∈1，X v ∈2， ，一般地，X v i ∈2，Y v i ∈+12，（ ,1,0=i ）。又因X v ∈0，故Y v k ∈，因而k 是奇数。注意到圈C 上共有1+k 条边，因此是偶圈。 充分性：设G 不含奇圈。取)(G V u ∈，令
}),(|)({odd v u d G V v X ＝∈=，}),(|)({even v u d G V v Y ＝∈=。
任取一条边21v v e =，欲证21,v v 分属于X 和Y 。设P ，Q 分别是u 到21,v v 的最短路。 （1）如果12v v Q P +=或21v v P Q +=，则21,v v 到u 的距离奇偶性相反，21,v v 分属于X 和Y 。
（2）否则，设u ′是P 与Q 的最后一个公共顶点，因P 的),(u u ′段和Q 的),(u u ′段都是u 到u ′的最短路，故这两段长度相等。
假如P ，Q 的奇偶性相同，则P 的),(1v u ′段和Q 的),(2v u ′段奇偶性相同，这两段与边e 构成一个奇圈，与定理条件矛盾。可见P ，Q 的奇偶性不同，从而21,v v 分属于X 和Y 。
这便证明了G 是一个二部图。 证毕。 例1.1.5判断下列图是不是二部图。
Peterson 图
解：Herschel 图的一个顶点二划分如下：
可见Herschel
Peterson图中含有奇圈，因此不是二部图。
7. 连通性
图中两点的连通：如果在图G中u，v两点间有路相通，则称顶点u，v在图G中连通。
连通图（connected graph）：若图G中任二顶点都连通，则称图G是连通图。
图的连通分支（connected branch, component）：若图G的顶点集V(G)可划分为若干非空子集ω
V
V
V,
,
,
2
1
，使得两顶点属于同一子集当且仅当它们在G中连通，则称每个子图]
[
i
V
G为图G的一个连通分支（ω,
,2,1
=
i）。
注：（1）图G的连通分支是G的一个极大连通子图。
（2）图G连通当且仅当1
＝
ω。
例1.1.6设有2n个电话交换台，每个台与至少n个台有直通线路，则该交换系统中任二台均可实现通话。
证明：构造图G如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线路。问题化为：已知图G有2n个顶点，且n
G≥
)
(
δ，求证G连通。
事实上，假如G不连通，则至少有一个连通分支的顶点数不超过n。在此连通分支中，顶点的度至多是1
?
n。这与n
G≥
)
(
δ矛盾。证毕。
例1.1.7若图中只有两个奇度顶点，则它们必连通。
证明：用反证法。假如u与v不连通，则它们必分属于不同的连通分支。将每个分支看成一个图时，其中只有一个奇度顶点。这与推论1.1.1矛盾。证毕。
8. 图的同构
我们已经知道，同一个图可以有不同形状的图示。反过来，两个不同的图也可以有形状相同的图示。比如：
易见
1
G和
2
G的顶点及边之间都一一对应，且连接关系完全相同，只是顶点和边的名称不同而已。这样的两个图称为是同构的(isomorphic)。
从数学上看，同构的两个图，其顶点间可建立一一对应，边之间也能建立一一对应，且若一图的两点间有边，则在另一图中对应的两点间有对应的边。严格的数学定义如下。 定义1.1.1 对两个图))(),((G E G V G =与))(),((H E H V H =，如果存在两个一一映射：
)()(:H V G V →α，)()(:H E G E →β，
使得对任意)(),(G E v u e ∈=，都有)())(),((H E v u ∈αα且=)(e β))(),((v u αα，则称图G 与H 同构，记为H G ?。
图的同构关系是一种等价关系（即满足反身性、对称性、传递性），这种等价关系将υ阶图分成若干等价类，彼此同构的图属于同一类。同一个等价类中的图有相同的结构，差别仅在于顶点和边的名称不同。由于人们关心的是图的结构，因此，通常将同构图类中的所有图看成同一个图，而不在乎它们顶点和边的名称以及它们的图示画法。在图的图示中，不给顶点和边标定名称的图称为非标定图，否则称为标定图。非标定图实际上就是一个同构图类的代表。在不致误解的情况下，我们也往往不严格区分标定图与非标定图。
目前尚无简便的方法判别两个图是否同构，特别是当图的顶点数较大时，判断两个图是否同构是一件很困难的事情。
两图同构，首先它们的阶必须相等，边数必须相等；其次要有相同的环边、重边及圈的状态；还应保持顶点的度，即在同构映射下相对应的顶点必须有相同的度。这些都是两图同构的必要条件，可用来判断两图不同构。
为判定两图同构，一般要按定义构造出两图顶点间的一一映射，然后检验它是否保持邻接关系。有时也可根据图的特点使用特殊方法。 例1.1.8判断下列图是否同构
解：图G 1和G 2 是同构的。事实上，定义它们顶点间的映射f ，分别将顶点v 1, v 2, v 3, v 4, v 5, v 6映射到u 1, u 3, u 5, u 2, u 4, u 6，显然这是G 1到G 2的一个一一映射，且容易验证它保持顶点间的相邻关系。
图G 2和G 3 也是同构的。
事实上，定义它们顶点间的映射g ，分别将顶点u 1, u 2, u 3, u 4, u 5, u 6映射到w 1, w 2, w 3, w 4, w 5, w 6，显然这是G 2到G 3的一个一一映射，且容易验证它保持顶点间的相邻关系。
图G 3和G 4 不同构，因为G 4含有三角形（即子图K 3），但G 3不含。
注：（1）G 1、G 2、G 3的同构性还可以通过它们的二部图特性来证明。可以检验，它们都是完全二部图K 3,3。
（2）容易证明，两个图G 和H 同构当且仅当它们的补图G H 、同构。利用这一结论，也可以较简便地判定G 1、G 2、G 3的同构性，事实上，G 1、G 2、G 3的补图都是两个不相交的C 3（长为 3的圈）
，因此同构。而G 4的补图是C 6，故G 4与前三个图不同构。
关于图的同构有两个猜想至今尚未解决。 猜想1（Ulam 重构猜想，1929）设G 与H 是两个图，
|V(G)| = |V(H)|, V(G) = {u 1, u 2, ???, u n }，V(H)={v 1, v 2, ???, v n }。
若对{1,2,,}i n ?∈ ，都有i i G u H v ???，则G H ?。其中i G v ?表示将v i 以及与v i 关联的边都从G 中删除后所得之图，i H v ?类似。
猜想2设G 与H 都是至少有四条边的图，若存在一一映射:()()E G E H ?→，使得对
()e E G ?∈，都有()G e H e ????，则G H ?。
有关图的重构问题的更多内容可参看:
[1] C.St.J.A. Nash-Williams, The reconstruction problem, in Selected Topics in Graph Theory (L. W. Beineke and R.J. Wilson eds.), Academic Press, London, (1978) 205-236.
[2]W.T. Tutte, Graph Theory, Cambridge University Press, (2001) 115-124.(影印版：图论，机械工业出版社，2004).
§1.2 最短路问题
一、赋权图
给图G 的每条边e 赋以一个实数w (e )，称为边e 的权。每条边都赋有权的图称为赋权图。
权在不同的问题中会有不同的含义。例如交通网络中，权可能表示运费、里程或道路的造价等。
设H 是赋权图G 的一个子图，H 的权定义为)(H W ＝∑∈)
()(H E e e w ，特别地，对G 中一
条路P ，其权为)(P W ＝
∑∈)
()(P E e e w 。
二、最短路问题
最短路问题：给定赋权图G 及G 中两点u , v ，求u 到v 的具有最小权的路（称为u 到v 的最短路）。 注：赋权图中路的权也称为路的长，最短(u ,v )路的长也称为u ,v 间的距离，记为d (u ,v )。 最短路问题是一个优化问题，属于网络优化和组合优化的范畴。对这种优化问题的解答一般是一个算法。最短路问题有很多算法，其中最基本的一个是Dijkstra 算法。 三、Dijkstra 算法 1. 算法思想
设赋权图G 中所有边都具有非负权，Dijkstra 算法的目标是求出G 中某个指定顶点0v 到其它所有点的最短路。它依据的基本原理是：若路011k k P v v v v ?= 是从0v 到k v 的最短路，则011k P v v v ?′= 必是从0v 到1k v ?的最短路。基于这一原理，算法由近及远地逐次求出0v 到其它各点的最短路。
下面通过例子说明具体做法。
图1.1
（1）令0{}S v =，\S V S =，求0v 到S 中最近点的最短路。在当前的例子中，从v 0v 1、
v 0v 2、v 0v 3中选一条最短的，结果获得v 0到v 1的最短路v 0v 1。
（2）令1:{}S S v =∪，:\S V S =，求0v 到S 中最近点的最短路。这里“最近”是指0v 到S 的直接连边、以及从0v 出发的已有最短路上的点（即S 中除0v 外的点，当前只有1v ）通过最短路再添加上向S 的连边所形成的路中最短的。即选取S 中一点v 使得距离
00,(,)min {(,)()}i i i v S v S
d v v d v v w v v ∈∈=+。 (*)
在当前的例子中，从v 0v 2、v 0v 3、v 0v 1v 2、v 0v 1v 3中选一条最短的，结果获得v 0到v 3的最短路
v 0v 1v 3。
（3）令3:{}S S v =∪，:\S V S =，求0v 到S 中最近点的最短路。即选取S 中一点v 使得
00,(,)min {(,)()}i i i v S v S
d v v d v v w v v ∈∈=+。
当前应从v 0v 2、v 0v 1v 2、v 0v 1v 3v 2、v 0v 1v 3v 4中选一条最短的，结果获得v 0到v 4的最短路v 0v 1v 3v 4。 （4）令4:{}S S v =∪，:\S V S =，求0v 到S 中最近点的最短路。即选取S 中一点v 使得
00,(,)min {(,)()}i i i v S v S
d v v d v v w v v ∈∈=+。
当前应从v 0v 2、v 0v 1v 2、v 0v 1v 3v 2、v 0v 1v 3v 4 v 2中选一条最短的，结果获得v 0到v 2的最短路v 0v 1v 2（或v 0v 1v 3v 4 v 2）。
一般地，若01{,,,}k S v v v = 以及相应的最短路已找到，则可用(*)式来选取v ，获得0
v 到v 的最短路。 2．算法实现－标号法
在上述算法的过程中，每轮循环求0(,)d v v 时，都要对所有的点i v S ∈计算
0(,)()i i d v v w v v +且比较出一个最小的值，因而在算法循环过程中需要大量重复的路长计
算和比较。为了避免这种重复计算，Dijkstra 算法采用标号方法来实现：算法执行中，给每个点v 都附一个标号l (v )，表示当前已经算出的从v 0到该点的最短路的长0(,)d v v 。算法每轮循环都考虑修改点v 的标号，如果通过此前刚刚进入S 集合的点v i 到该点的连边不能获得更短的路，则该点保持原有标号l (v )不变；否则，修改该点标号为l (v ): = l (v i ) + w (v i v )，当前
v 0到v 的最短路应由v 0到v i 的最短路及边v i v 构成。
标号法的基本原理是累进比较。初始时，0():0l v =，∞=:)(v l ，（0v v ≠），0{}S v =，
\S V S =。然后算法逐步修改S 中顶点的标号。第i 步时，对S 中每个v ，只对刚进入S
的点v i 计算0(,)()i i d v v w v v +（即()()i i l v w v v +），并与()l v 进行比较，取其较小的一个作为的新标号，即():min{(),()()}i i l v l v l v w v v =+。因为对在i v 之前进入S 的点
011,,,i v v v ? ，0(,)()k k d v v w v v +（k = 1, 2, …, i ?1）的值及其大小信息已含于()l v 之中，
因此只需计算一个值0(,)()i i d v v w v v +，并将其与此前纪录的最短路的长()l v 进行比较即可，而不必对所有的点i v S ∈都重新计算0(,)()i i d v v w v v +且比较出一个最小的，从而避免了重复计算和比较。
按照算法过程，标号法实现算法主要包括两个过程，（1）修改各点的标号，（2）从S 的所有点中取标号最小的一个点，放入S 中。某个点被放入S 集合后，它的标号成为永久标号，不再被修改。算法反复执行上述过程，直至所有顶点获得永久标号（被放入S 中）
。 算法具体步骤如下：
Dijkstra 算法：求非负权图中v 0点到其余各点的最短路。
第1步. 令0():0l v =，∞=:)(v l ，（0v v ≠），0:{}S v =, :\S V S =，0:=i 。 第2步. 对每个v S ∈，令():min{(),()()}i i l v l v l v w v v =+。
取*v S ∈ 使得 (*)min{()}v S
l v l v ∈=。记 *1i v v +=, 令1:{}i S S v +=∪, :\S V S =。
第3步. 令1:+=i i 。如果1i υ=?, 则停止；否则，转第2步。 3. 算法正确性
定理1.2.1 Dijkstra 算法结束时，对任一个顶点v ，其标号l (v )恰是v 0到v 的最短路的长。 证明：按照算法，顶点v 的最终标号l (v )是v 进入集合S 时的标号。假设v 在算法第i 次循环时进入集合S ，则1i v v +=，且v 进入集合S 后{,,,,}011i i S v v v v += 。由于l (v )是算法在前i 次循环中逐次比较出的当前从v 0到v 最短路的长，因此从v 0到v 仅含{,,,,}011i i v v v v + 中点的任何路的长都不会小于l (v )。任取图G 中一条从v 0到v 的路P ，如果P 仅含
{,,,,}011i i v v v v + 中的点，则如上所述，P 的长不会小于l (v )；如果P 含{,,,,}
011i i v v v v + 之外的点，无妨设沿着P 从v 0出发第一个不在{,,,,}011i i v v v v + 中的顶点是v ′。因在算法第i 次循环时，v i +1进入S 而v ′ 仍未进入S ，说明当前l (v i +1)≤ l (v ′ )。注意v ′ 只是P 的中途点且图G 中所有边的权都非负，而当前的l (v ′ )大于或等于v 0到v ′ 仅含{,,,,}011i i v v v v + 中点的最短路的长，故路P 的长大于或等于P 上v 0到v ′ 段的长（≥ l (v ′ )），从而P 的长不会小于l (v i +1)（即l (v )）
。 证毕。 按照上述定理，Dijkstra 算法结束时，每个顶点的标号l (v )表示v 0到该点的最短路的长。此外，通过检查标号的来源点，可反向追踪得到v 0到各点的最短路。 4. 算法有效性
对于一个图论算法，如果在任何图上施行这个算法所需要的基本计算量（比如加、减、
乘、除运算或比较、赋值等）都以图的顶点数υ的一个函数为其上界，则称这个函数为该算法的计算复杂度或时间复杂度，一般简称为复杂度（complexity ）。图的顶点数υ称为图论问题的规模。人们总是希望利用计算机执行算法以解决人工难以计算的大规模问题，因此，对一个算法人们主要关心它在解决大规模问题时的计算量。对于图论算法，主要关心当图的顶点数υ增大时，算法所需计算量的增加情况。如果一个算法的计算复杂度是规模υ的指数函数，比如2υ
、!υ等，则当问题的规模较大时，算法所需的计算量快速增大以至于无法接受，这样的算法在解决大规模问题时实际上是无用的。当一个算法的计算复杂度是多项式函数时，算法的计算量随规模的增加其增幅较缓，人们认为一般是可以接受的。因此，一个具有多项式时间复杂度的算法称为是有效算法（efficient algorithm ）或好算法(good algorithm ），有时直接称为多项式时间算法或多项式算法。对于多项式算法，影响其时间复杂度的主项是多项式的最高次项，因此人们在作算法分析时，主要关注其最高次项。一般地，如果一个算法的复杂度是1
110k
k k k a a a a υυ
υ??++++ ，则我们说它的计算复杂度是()k O υ，或是
()k O υ阶的。利用这个记号，如果一个算法的复杂度是2υ或!υ，我们也可写为O(2)υ或 O(!)υ。
按照复杂度的上述定义，如果一个算法是()k
O υ阶的，则它也是1
()k O υ
+阶的，甚至也
是O(2)υ
阶的。但实际上，人们在提到算法的复杂性时，总是指它的最低的阶。
下一定理表明Dijkstra 算法是多项式算法。 定理1.2.2 Dijkstra 算法的计算复杂度为()2
O υ。
证明：Dijkstra 算法的主要计算量在第2步。在第i 次循环中，第2步第1式需要1i υ??次加法，1i υ??次比较；
第2式需要不超过1i υ??次比较。(0,1,,2i υ=? )。从而1υ?次循环总的计算量不超过
2
3(1)i i νυ?=??=
∑3(1)2
υυ?= ()2
O υ。 对一个需要用算法解决的问题，如果存在求解它的多项式算法，则这个问题称为P 问题(polynomial problem)。如果一个问题，当猜出其答案时可在多项式计算量内验证答案的正确性，则这个问题称为NP 问题(non-deterministic polynomial problem)。将所有P 问题的集合记为P ，所有NP 问题的集合记为NP ，是否P=NP ？这是计算机科学和组合最优化领域的一个重要未解难题。明显地P NP ?，但人们目前还不知道是否P NP ?。Cook(1970)发现
NP 问题中有一类问题，只要其中有一个问题是P 问题，则所有NP 问题全是P 问题，即
P=NP 。这类问题称为NP 完全问题，简称为NPC 问题(non-deterministic polynomial problem)。
遗憾的是，对目前已找到的成千上万个NPC 问题，人们还未能证明其中任何一个是P 问题。图论中有许多问题属于NPC 问题。有兴趣的读者可参阅下列文献。
[2] http://www.nada.kth.se/~viggo/problemlist/
[3] M. R. Garey & D. S. Johnson, Computers and Intractability ? a guid to the theory of NP-completeness, W. H. Freedman, San Francisco, 1979. （中译本：张立昂等译，计算机和难解性—NP 完全性理论导引，科学出版社，1987）
。 [4] D.S. Hochbaum, Approximation algorithms for NP-hard problems, International Thomson
Publishing Company, 1995.
[5] Ding-zhu Du and Ker-I Ko, Theory of Computational Complexity, John Wiley & Sons, INC., New York, 2000.
[6] Feng Gao, Ding-zhu Du, Biao Gao, Peng-jun Wan, and P. M. Pardalos, Minimax problems in combinatorial optimization, Minmax and Applications (eds. by Ding-zhu Du & P. M. Pardalos), Kluwer Academic Publishers, 1995.
[7] D.B.Shmoys, Computing near-optimal solutions to combinatorial optimization problems, Combinatorial Optimization (W.Cook, L.Lovasz and P.Seymour eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, V ol.20, (1995) 355-397.
[8] C.H. Papadimitriou & K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1982.
[9] A. Gibbons, Algorithmic graph theory, Cambridge, Cambridge University Press, 1985. [10] M. R. Garey & D. S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems, Theoret. Comput. Sci., I 237-267, 1976.
[11] Cook S. The complexity of theorem-proving procedure, Conference Record of Third ACM Symposium on Theory of Computing, 1970, pp151-158. [12] 王树禾，图论及其算法，中国科技大学出版社，1990。
[13] 谢政，网络算法与复杂性理论（第二版），国防科技大学出版社，2003。
上述Dijkstra 算法可以用列表的方式进行计算，下面举例说明。
考虑图1.1中的赋权图。首先将顶点v 1，v 2，v 3，v 4作为一行。然后将起始点v 0放在表内第一行左首，将v 0到其余各点连边上的权（即标号l (v k )）放在各顶点下方相应位置上。从第一行数字中选取最小的一个，用方括号标记，并在斜杠下方标上v 0，当前找到v 1下方的数字最小。接着，将v 1放在表内第二行左首（表示v 1进入集合S ）
，对每个尚未进入S 的顶点v k ，将第一行方括号中的数字与边v 1v k 上的权相加，并与第一行v k 下方的数字比较，取较小的一个（即新标号():min{(),()()}11k k k l v l v l v w v v =+）放在第二行相应位置上。从第二行数字中选取最小的一个，用方括号标记，当前找到v 3下方的数字最小。由于该数字3是通过v 1得来的（即min{(),()()}3113l v l v w v v +113()()3l v w v v =+=），故在该数字斜杠下方标上v 1。
同样，将v 3放在表内第三行左首（表示v 3进入集合S ），对每个尚未进入S 的顶点v k ，
将第一行方括号中的数字与边v 3v k 上的权相加，并与第二行v k 下方的数字比较，取较小的一个（即新标号():min{(),()()}33k k k l v l v l v w v v =+）放在第三行相应位置上。并从第三行数字中选取最小的一个，用方括号标记，当前找到v 4下方的数字最小。由于该数字5是通过v 3得来的（即min{(),()()}4334l v l v w v v +334()()5l v w v v =+=），故在该数字斜杠下方标上v 3。最后，将v 4放在表内第四行左首（表示v 4进入集合S ）
，对尚未进入S 的唯一顶点v 2，将第一行方括号中的数字与边v 3v 2上的权相加，并与第三行v 2下方的数字比较，取较小的一个（即新标号():min{(),()()}22442l v l v l v w v v =+）放在第四行相应位置上。并从第四行数字中选取最小的一个，现在第四行只有v 2下方的数字6，用方括号标记之，v 2进入集合S 。由于该数字6可看成是通过v 2的旧标号l (v 2)得来的（即
min{(),()()}2442l v l v w v v +2()6l v ==），旧标号l (v 2)又是在第二行通过v 1得来的，故在
该数字斜杠下方标上v 1。至此，算法结束。从每个顶点v k 所在列的最后一个数字（方括号内的数字）可以得知v 0到v k 的最短路的长。比如，v 0到v 4的最短路的长为5。
由斜杠后的标识可反向追踪出最短路。比如找v 0到v 4的最短路：先从v 4列下方的标识找到v 3，再从v 3列下方的标识找到v 1，最后从v 1列下方的标识找到v 0，从而可知v 0到v 4的最短路为v 0 v 1 v 3 v 4。
Dijkstra 算法也可以通过矩阵形式来进行，其步骤为：
第0步. 将赋权图G 的权矩阵(w ij )的第一列中所有元素全改为×，在第一行剩下的其他元素下面划一条横线。
第1步. 在画横线的元素中找一个最小的w ki ，若w ki =∞，则停止，从v 0 到某些顶点没有路；否则，把w ki 用方括号标记，并把第i 列其他元素都改成×，然后给第i 行中不是×的元素都加上w ki ，并在这些元素下面划一条横线，转第2步。
第2步. 如果存在不含×的列，则转第1步；否则结束，方括号标记的元素w ij 表示从v 0到v j 的最短路的长，而从v 0到v j 的最短路由最短(v 0,v i )路与边v i v j 构成。
仍以图1.1为例，其权矩阵为
(w ij ) =
1234
01
234
1841528561426212v v v v v v v v v v ∞∞????∞∞????∞??∞????∞∞∞?? 1841528561426212
∞∞????∞∞????∞??∞????∞∞∞?
??1
84525612621
2
×
∞????×∞∞????×∞??×
∞????×
∞∞???[1]846361621
2
×
∞??
??××∞????××∞??×
×∞????××
∞??
?
[1]8
6[3]
1
95
1
××∞
??
??
××∞
??
??
××∞×
??
×××
??
??
×××∞
??
?
[1]8
6[3]
9[5]
6
×××
??
??
×××
??
??
××∞××
??
×××
??
??
××××
??
?
[1]
[6][3]
[5]
××××
??
??
×××
??
??
×××××
??
××××
??
??
×××××
??
由最后一个矩阵的元素回溯便可获得v0到各点的最短路。比如，v4的最短路的长为5；
为找从v0到v4的最短路，从v4所在列（最后一列）开始回溯，因该列非×元素在v3行（第4行），v3列非×元素在v1行（第2行），而v1列非×元素在v0行（第1行），故v0到v4的最短路为v0 v1 v3 v4。
上述最短路算法仅适用于求所有边的权均非负的途中的最短路。在边允许有负权的图中求最短路，有Ford算法和Floyd算法。Ford算法用于求无负权圈的图中一点到其它各点的最短路；Floyd算法用于求无负权圈的图中所有顶点对之间的最短路。这两个算法当然也可以用于所有边的权均为非负的图中。有兴趣的读者可参看文献[14]、[15]、[16]。求图的前k 条最短路的算法可参考[16]。
[14] 谢政，网络算法与复杂性理论（第二版），国防科技大学出版社，2003。
[15] 王朝瑞，图论（第三版），北京理工大学出版社，2001。
[16] N. Christofides, Graph Theory–a algorithmic approach, Academic Press, INC., 1990.
此外，对分层图，也可用动态规划方法来求最短路。动态规划源于多阶段最优决策过程，它的基本思想是Bellman最优化原理。该原理可概括地描述为：如果图G中从A点到C点的最短路P经过点B，则P上B到C的一段必定是该图中B点到C点的最短路。依据这个原理，可用一个基本的递推关系式使最优决策过程连续地转移。使用动态规划方法时，要从最终状态开始逐步递推到起始状态。例如，对下图求A到H的最短路。
该图的顶点从A到F分为5层，同层顶点间互不连边，隔层顶点间也没有连边，这便是分层图。我们从H点开始考虑。其前一层顶点F和G到H的最短路的长分别是4 和3，记为W(F)=4，W(G)=3。再考虑F和G的前一层顶点D和E。从D出发有两种选择：DFH，路长为1+ W(F)=5；DGH，路长为1+ W(G)=4；故从D到H的最短路为DGH，W(D)=4。同样可知，从E到H的最短路为EGH，W(E)=5。再考虑B、C。B到H可经过D也可经过E，经D到H的最短路长为6+W(D)=10，经E到H的最短路长为6+W(E)=11，故从B到H 的最短路应经过D，且最短路长为W(B)=10。同样可得，从C到H的最短路应经过D，且最短路长为W(C)=8。最后考虑顶点A，它到H可经过B也可经过C，经B到H的最短路长为4+W(B)=14，经C到H的最短路长为5+W(C)=13，故从A到H的最短路应经过C，且最短路长为W(A)=13。因此获得A到H的最短路为ACDGH。
在上述过程中，决定每层顶点的结果只需要做4次加法。如果将图扩展为n 层，则计算量为4(n ?3)+2，这比Dijkstra 算法的计算量低的多。由此可见，针对具体问题的特点可以设计出非常有效的算法。
关于最短路问题读者可进一步参阅文献：
[17] E. Dijkstra, A note on two problem in connection with graphs, Numer. Math., 1(1959) 269-271.
[18] L.R. Ford, Network flow theory, Rand Corporation Report, (1956) 923. [19] R.W. Floyed, Algorithm 97- Shortest Path , Comm., ACM, 5(1962) 345.
[20] D. Bertsekas ，A simple and fast label correcting algorithm for shortest paths, Networks, 23(1993) 703-709.
[21] M. Desrochers, and F. Soumis, a reoptimization algorithm for the shortest path problem with time windows, Europaean Journal of Operational Research, 35(1988) 242-254.
[22] M.Dror, Note on the complexity of the shortest path models for column generation, Operations Research, 42(1994) 977-978.
[23] G . Gallo, and S. Pallottino, Shortest path algorithms, Annals of Operations Research, 7(1988) 73-79.
[24] F. Glover, R. Glover, and D. Klingman, The threshold shortest path algorithm, Networks, 14(1984) 25-36.
[25] W.B. Powell, Zhi-Long Chen, A generalized threshold algorithm for the shortest path problem with time windows, in Network Design: Connectivity and Facilities Location (P.M. Pardalos and Ding-zhu Du eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, V ol.40, (1998) 303-318.
§1.3 树及其性质
不含圈的图称为森林(forest)，不含圈的连通图称为树（tree ）。 定理1.3.1 下列命题等价： （1） G 是树；
（2） G 中无环边且任二顶点之间有且仅有一条路； （3） G 中无圈且1ευ=?； （4） G 连通且1ευ=?;
（5） G 连通且对任何)(G E e ∈，e G ?不连通； （6） G 无圈且对任何(G E e ∈，e G +恰有一个圈。 证明：（1）?（2）
G 是树?G 连通?)(,G V v u ∈?，存在路),(v u P 。
若还存在一条路≠′),(v u P ),(v u P ，则必存在w ，w 是路P 与P ′除了v 之外最后一个公共顶点。P 的),(v w 段与P ′的),(v w 段构成圈，这与G 是树矛盾。故只存在唯一的),(v u 路。
（2）?（3）
若G 有圈，则此圈上任二顶点间有两条不同的路，与前提条件矛盾。 下面用归纳法证明1ευ=?。
1υ=时，0=ε，结论真。
假设k υ≤时结论真，我们来证明当1k υ=+时，也有1ευ=?成立。
当1k υ=+时，任取边E()uv G ∈。考虑图uv G G ?=′，因G 中u 、v 间只有一条路，即边uv ，故G ′不连通且只有两个连通分支，设为21,G G 。注意到21,G G 分别都连通且任二顶点间只有一条路，由归纳法假设，11()()1G G ευ=?，22()()1G G ευ=?。因此
1212()()()1(()1)(()1)1()1G G G G G G εεευυυ=++=?+?+=?。
归纳法完成。 （3）?（4）
用反证法。若G 不连通，设w G G G ,,,21 是其连通分支（2≥w ），则1i i ευ=?（因
i G 是连通无圈图，由已证明的(1)和(2)知，对每个i G ，（3）成立）。这样，
1
1
w w
i i i i w w εευυ====?=?∑∑，这与1ευ=?矛盾。
（4）?（5）
()()12G e G εευ?=?=?，但每个连通图必满足1ευ≥?（见下列引理），故图
e G ?不连通。
引理 若图H 连通，则()()1H H ευ≥?。 证明：对υ做数学归纳法。
1,2υ=时，1ευ≥?显然成立。
假设k υ≤的连通图都1ευ≥?。
对于1k υ=+的连通图H ，任取)(H V v ∈，考虑v H ?。
若v H ?连通，则由归纳假设，()()11H v H v k ευ?≥??=?，而
()()1(1)1(1)1()1H H v k k H εευ≥?+≥?+=+?=?。
若v H ?不连通，设w H H H ,,,21 是其连通分支(2≥w )。由归纳假设，
()()1i i H H ευ≥?，(w i ,,2,1 =)。故
1
1
()()()()w
w
i i i i H v H H w H v w k w εευυ==?=≥?=??=?∑∑，
而()()()(1)1()1H H v w k w w k H εευ≥?+≥?+=+?=?。
归纳法完成。 （5）?（6）
先证G 中无圈：若G 中有圈，删去圈上任一边仍连通，矛盾。
再证对任何)(G E e ∈，e G +恰含一个圈：因G 连通且已证G 无圈，故G 是树。由（2）
，任二不相邻顶点间都有一条路相连，故e G +中必有一个含有e 的圈；另一方面，若e G +中有两个圈含有e ，则(e G +)G e =?中仍含有一个圈，矛盾。
（6）?（1）
只需证G 连通。任取)(,G V v u ∈，若u 、v 相邻，则u 与v 当然连通。若u 、v 不相邻，则uv G +恰含一个圈，故u 与v 在G 中连通。由u 、v 的任意性，图G 连通。
定理证毕。
推论1.3.1 非平凡树至少含两个1度顶点（叶子）。
证明：设T 是一个非平凡树。因T 连通，故对每个顶点i v ，都有1)(≥i v d 。若对所有
i v 都有2)(≥i v d ，则1
()2i i d v υυ=≥∑。但另一方面，1
()22(1)22i i d v υ
ευυ===?=?∑。
这两方面矛盾。故T 至少有一个1度顶点，设为u 。除此之外，其余1υ?个顶点的度数之和为23υ?。若这些点的度都大于或等于2，则其度数之和2(1)22υυ≥?=?。这与
23υ?矛盾。故除u 之外T 还至少有一个度为1 的顶点。证毕。
§1.4 生成树与最小生成树
一、生成树（spanning tree ）
定义1.4.1 设T 是图G 的一个子图，如果T 是一棵树，且()()T G υυ=，则称T 是G 的一个生成树。
定理1.4.1 每个连通图都有生成树。
证明：设G 是一个连通图。令G G A ′′=|{是G 的连通子图且()()}G G υυ′=。易见A 非空。从A 中取边数最少的一个，记为T 。下证T 是G 的生成树。显然只需证明T 是树即可。
事实上，已知T 连通，下证T 无圈。
若T 有圈C ，则去掉C 上任一条边e ，e T ?仍连通。从而A e T ??。但e T ?比T 少一条边，这与T 的取法矛盾。证毕。 推论1.4.1 若G 连通，则1ευ≥?。
证明：取G 的生成树T ，则()()()1()1G T T G εευυ≥≥?=?。证毕。
二、最小生成树问题
最小生成树问题：在赋权图G 中，求权最小的生成树（简称为最小生成树）。即：求G 的一棵生成树T ，使得
∑∈=T
e T
e w T w )(min )(。
最小生成树问题是一个优化问题，需要设计优化算法寻找其最优解。求解最小生成树问题的算法较多，本节主要介绍Kruskal 算法和Prim 算法。 （一） Kruskal 算法(Joseph Bernard Kruskal, 1956)
1. 算法思想：先从图G 中找出权最小的一条边作为最小生成树的边，然后逐次从剩余边中选边添入最小生成树中，每次选边找出不与已选边构成圈的权最小的一条边。直至选出
(G)1υ?条边为止。
2. 算法步骤：输入：赋权连通υ阶图G 。输出：G 的最小生成树T 。 第一步 取)(1G E e ∈使得()min{()},e G
w e w e ∈=令:1i =。
第二步 取},,,{\)(211i i e e e G E e ∈+使得
(1) G[{121,,,,+i i e e e e }] 不含圈； (2) 1+i e 是满足(1)的权最小的边。
第三步 当 i +1 =
()1G υ?时, 输出最小生成树G[{121,,,e e e υ? }]，算法停止; 否则, 令
1:+=i i , 转第二步。
3. 算法正确性：
定理1.4.2 设12()1,,,G e e e υ? 是Kruskal 算法获得的边，则边导出子图G[{12()1,,,G e e e υ? }]是G 的最小生成树。
证明：记*T = G[{12()1,,,G e e e υ? }]。显然*T 无圈，因此*
T 是森林。设它有w 个连通分支，则 (T )(T )(T )1((G)1)1(G)w υεευυ?
?
?
=+≥+=?+=。 但*
T 是G 的子图，故*
()()T G υυ=。于是
**()()1()1T G T ευυ=?=?。
由定理1.3.1的(3)，*
T 是一棵树。又*
()()T G υυ=，从而是G 的一棵生成树。
下证其最优性，用反证法。
假设*
T 不是权最小的生成树(下称最优树)。对G 的任一棵不同于*
T 的生成树T ，记
121()min{|{,,,}i f T i e e e e υ?=∈ 且}T e i ?。
在Ｇ的所有最优树中选取一棵使)(T f 最大的，记为T ~。(T ~
不会是*T ，因假设*
T 不是最优树)。设k T f =)~(。由)~
(T f 的定义，121,,,?k e e e 既在*
T 上也在T ~
上，但k e 不在
T ~上。因此k e T +~含有一个圈C 。C 上必有一条边*T e k
?′。显然k k e e T T ′?+=′)~
(也是一棵生成树，且)()()~
()(k
k e w e w T w T w ′?+=′。 按照算法，k e 是使G[{k e e e ,,,21 }]中无圈的边中权最小的。注意
G[{k
k e e e e ′?,,,,121 }] 是T ~
的子图，也无圈。故由算法规则知：)()(k k e w e w ≥′。由前式，)~()(T w T w ≤′，这说明T ′也是最优树。但)~()(T f k T f =>′（注意由于121,,,?k e e e 在*
T 上且*T e k ?′，故121{,,,}k k e e e e ?′? ）。这与T ~
的取法矛盾。证毕。
4. Kruskal 算法的实现及其计算复杂度分析
Kruskal 算法的计算量主要在第二步。算法共需执行1υ?次第二步，在第i 次执行第二步时，须比较集合12()\{,,,}i E G e e e 中所有边的权以求得一条权最小的边，并检验该边是否与已有边构成圈，如果构成圈，还需再找新的最小权边，这是比较浪费的。
在实际应用Kruskal 算法时，一般先将所有的边按权由小到大排序，这需要大约2log εε次比较（见[26]）。每次执行算法第二步时，不必再比较边的权，而是直接选取此前尚未考虑过的权最小的边，检验它是否与已有边构成圈即可。这样可省去许多次循环比较。
[26] D.E. Knuth, The art of computer programming, V ol.3: Sorting and Searching, Addison-Wesley, Reading, Mass., (1973)184.
接下来的问题是如何检验所选边是否与已有边构成圈。这可通过给顶点标号来实现。设算法在i 次循环后选出的边集合为E i 。算法开始时，给所有顶点标不同的标号：顶点k v 标号为k ，（1,2,,k υ= ）。当算法执行第i +1次循环选出一边1i e +添加进G[E i ]形成G[E i +1]时，用该边两端点标号的较小者给这条边所连的G[E i +1]的两个连通分支的顶点重新标号（连通分支有可能仅由1i e +的一个端点组成）
。按这个标号方案，在任意一步中，两个顶点属于已选边形成的同一连通分支当且仅当它们有相同的标号。这意味着当我们考虑向G[E i ]添加某条边e 是否会形成圈时，只要检查e 的两个端点是否有相同的标号即可。如果有相同的标号，则抛弃该边（以后的循环中不再使用），再检验权稍大些的下一个候选边；如果标号相异，则取e 作为1i e +添加进G[E i ]。在这个过程中，对每条候选边只需做一次比较就能决定是否抛弃它。算法全过程至多需要ε(1)
2
υυ?≤
次这样的比较。
当添加1i e +进入G[E i ]时，顶点重新标号最多需要υ次比较，因此对1υ?条边最多需要
(1)υυ?次比较。
可见算法执行过程约需要ε+(1)υυ?次计算。 由以上分析可得如下结论。
定理1.4.3若事先将顶点按权排序，则Kruskal 算法的计算复杂度为2
O()υ；若加上事先排序的计算量，则Kruskal 算法的计算复杂度为2
2O(log )υυ。 证明：算法执行过程中需要的主要计算量为ε+(1)υυ?(1)
2
υυ?≤+(1)υυ?=
3
(1)2
υυ?， 事先排序需要的计算量为2log εε22
2(1)
(1)
log log 2
2
υυυυυυ??≤≤。故知定理结论成
立。证毕。
例1.4.1 欲建设一个连接5个城市的光纤通信网络。各城市间线路的造价如图所示，求一个使总造价最少的线路建设方案。
图论讲义第2章-连通性
第二章 图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度也有高有低。例如，下列三个图都是连通图。对于图G 1，删除一条边或一个顶点便可使其变得不连通；而对于图G 2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图G 3，要破坏其连通性，则至少需要删除三条边或三个顶点。 本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。通过研究割边和割点来刻画1连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的2连通和k 连通性。 §2.1 割点和割边 定义2.1.1 设)(G V v ∈，如果)()(G w v G w >?，则称v 为G 的一个割点。 （注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。 例如，下图中u , v 两点是其割点。 定理2.1.1 如果点v 是简单图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得][1E G 和][2E G 恰好有一个公共顶点v 。 证明留作习题。 推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G ?不连通。 定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。 证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。 若0)(=v d ，则1K T ?，显然v 不是割点。 若1)(=v d ，则v T ?是有1)(??v T ν条边的无圈图，故是树。从而)(1)(T w v T w ==?。因此v 不是割点。 以上均与条件矛盾。 充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。路uvw 是T 中一条),(w u 路。因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>?。故v 是割点。证毕。
图论基础知识
图论基本知识 对于网络的研究，最早是从数学家开始的，其基本的理论就是图 论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识，请参考相关文献[1-5]。 本章只给出非平凡的定理的证明，过于简单直观的定理的证明将 留给读者。个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。 图的基本概念 图G 是指两个集合(V ，E)，其中集合E 是集合V×V 的一个子集。 集合V 称为图的顶点集，往往被用来代表实际系统中的个体，集合E 被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。若{,}x y E ，就称图G 中有一条从x 到y 的弧（有向边），记为x→
y ，其中顶点x 叫做弧的起点，顶点y 叫做弧的终点。根据定义，从任意顶点x 到y 至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析分析带来困难。如果再假设图G 中不含自己到自己的弧，我们就称图G 为简单图，或者更精确地叫做有向简单图。以后如果没有特殊的说明，所有出现的图都是简单图。记G 中顶点数为()||G V ν=，边数为()||G E ε=，分别叫做图G 的阶和规模，显然有()()(()1)G G G ενν≤-。图2.1a 给出了一个计算机分级网络的示意图，及其表示为顶点集和边集的形式。 图2.1：网络拓扑结构示意图。图a 是10阶有向图，顶点集为 {1,2,3,4,5,6,7,8,9,10}，边集为{1→2,1→3,1→4,2→5,2→6,2→7,3→6,4→7,4→8,6→9,7→9,8→10}；图b 是6阶无向图，顶点集为{1,2,3,4,5,6}，边集为{13,14,15,23,24,26,36,56}。 从定义中可以看到，从任意顶点x 到y 不能连接两条或以上 边，本文所讨论的图，均符合上述要求，既均为不含多重边的图。如
图论讲义第3章-匹配问题
第三章 匹配理论 §3.1 匹配与最大匹配 定义3.1.1 设G 是一个图, )(G E M ?，满足:对i e ?,M e j ∈，i e 与j e 在G 中不相邻，则称M 是G 的一个匹配。对匹配M 中每条边uv e =，其两端点 u 和 v 称为被匹配M 所匹配，而 u 和 v 都称为是M 饱和的(saturated vertex )。 注:每个顶点要么未被M 饱和, 要么仅被M 中一条边饱和。 定义3.1.2 设M 是G 的一个匹配, 若G 中无匹配M ′, 使得||||M M >′, 则称M 是G 的一个最大匹配；如果G 中每个点都是M 饱和的, 则称M 是G 的完美匹配(Perfect matching ). 显然, 完美匹配必是最大匹配。 例如，在下图G 1中，边集{e 1}、{e 1,e 2}、{e 1,e 2,e 3}都构成匹配，{e 1,e 2,e 3}是G 1的一个最大匹配。在 G 2中，边集{e 1,e 2,e 3,e 4}是一个完美匹配，也是一个最大匹配。 定义3.1.3 设M 是G 的一个匹配, G 的M 交错路是指其边M 和M G E \)(中交替出现的路。如果G 的一条M 交错路(alternating path)的起点和终点都是M 非饱和的，则称其为一条M 可扩展路或M 增广路(augmenting path)。 定理 3.1.1(Berge,1957) 图G 的匹配M 是最大匹配的充要条件是G 中不存在M 可扩展路。 证明:必要性:设M 是G 的一个最大匹配。如果G 中存在一个M 可扩展路P ,则将P 上所有不属于M 的边构成集合M ′。显然M ′也是G 的一个匹配且比M 多一条边。这与M 是最大匹配相矛盾。 充分性:设G 中不存在M 可扩展路。若匹配M 不是最大匹配，则存在另一匹配M ′,使 ||||M M >′. 令 ][M M G H ′⊕=，(M M M M M M ′?′=′⊕∩∪称为对称差)。 则H 中每个顶点的度非1即2(这是因为一个顶点最多只与M 的一条边及M ′的一条边相关联)。故H 的每个连通分支要么是M 的边与M ′的边交替出现的一个偶长度圈，要么是M 的边与M ′的边交替出现的一条路。 由于||||M M >′，H 的边中M ′的边多于M 的边，故必有H 的某个连通分支是一条路，且始于M ′的边又终止于M ′的边。这条路是一条M 可扩展路。这与条件矛盾。 证毕。
数学竞赛：图论讲义
数学竞赛：图论讲义 大连市第二十四中学 邰海峰 重要的概念与定理 完全图 每两个顶点之间均有边相连的简单图称为完全图,有n 个顶点的完全图(n 阶完全图)记为n K . 顶点的度 图G 中与顶点v 相关联的边数(环按2条边计算)称为顶点v 的度(或次数),记为()d v .()G δ与()G ?分别表示图G 的顶点的最小度与最大度.度为奇数的顶点称为奇顶点,度为偶数的顶点称为偶顶点. 树 没有圈的连通图称为树,用T 表示,其中度为1的顶点称为树叶(或悬挂点).n 阶树常表示为n T . k 部图 若图G 的顶点集V 可以分解为k 个两两不相交的非空子集的并,即 1,()k i i j i V V V V i j == =?≠ 并且同一子集i V (1,2,,)i k =内任何两个顶点没有边相连,则称这样的图为k 部图,记作12(,,,;)k G V V V E =. 2部图又叫做偶图,记为(,;)G X Y E =. 完全k 部图 在一个k 部图12(,,,;)k G V V V E =中,i i V m =(1,2,,)i k =,若对任意 ,,(,,1,2,,)i i j j v V v V i j i j k ∈∈≠=均有边连接i v 和j v ,则称图G 为完全k 部图,记为12,,,k m m m K . 欧拉迹 包含图中所有边的迹称为欧拉迹.起点与终点重合的欧拉迹称为闭欧拉迹. 欧拉图 包含欧拉迹的图为欧拉图. 欧拉图必是连通图. 哈密顿链(圈) 经过图上各顶点一次并且仅仅一次的链(圈)称为哈密顿链(圈).包含哈密顿圈的图称为哈密顿图. 平面图 若一个图G 可画在平面上,即可作一个与G 同构的图G ',使G '的顶点与边在同一平面内,且任意两边仅在端点相交,则图G 称为平面图. 一个平面图的顶点和边把一个平面分成若干个互相隔开的区域,称为平面图的一个面,在所有边的外面的面称为外部面,其余的称为内部面. 竞赛图 有向完全简单图称为竞赛图.有n 个顶点的竞赛图记作n K . 有向路 在有向图(,)D V U =中,一个由不同的弧组成的序列12,,,n u u u ,其中i u 的起点为i v ,终点为1(1,2,,)i v i n +=,称这个序列为从1v 到1n v +的有向路(简称路),n 为这个路的长,1v 为
图论讲义12 (1)
第八章独立集和团 §8.1 独立集 °独立集：设S是V的一个子集，若S中任意两个顶点在G中均不相邻，则称S为G的一个独立集。 °最大独立集：G的一个独立集S称为G的最大独立集，是说：G不包含适合S′>S的独立集S′。 °例子：(见图8.1) °覆盖：G的一个覆盖是指V的子集K，使得G的每条边都至少有一个端点属于K。 °例子：在图8.1中，两个独立集都是覆盖的补集。 定理8.1：设S?V，则S是G的独立集当且仅当V\S是G的覆盖。证：按定义，S是G的独立集当且仅当G中每条边的两个端点都不同时属于S，即当且仅当G的每条边至少有一个端点属于V\S，亦即当且仅当V\S是G的覆盖。? °独立数：G的最大独立集的顶点数称为G的独立数，记为α(G)。°覆盖数：G的最小覆盖的顶点数称为G的覆盖数，记为β(G)。 推论8.1：α+β=υ。 证：设S是G的一个最大独立集，K是G的一个最小覆盖。由定理8.1，V\K是独立集，而V\S是覆盖。因此 υ?β=V\K≤α (8.1) υ?α=V\S≥β (8.2)
结合8.1式和(8.2)式，即得α+β=υ。? °边覆盖：G的一个边覆盖是指E的一个子集L，使得G的每个顶点都是L中某条边的端点。 °边独立集：即对集。 *注意：边覆盖并不总是存在的，G有边覆盖，当且仅当δ>0。 °边独立数和边覆盖数：最大对集的边数称为边独立数，记作α′G;最小边覆盖的边数称为边覆盖数，记作β′(G)。 *注意：对集的补集不一定是边覆盖，边覆盖的补集也不一定是对集。定理8.2 (Gallai)：若δ>0,则α′+β′=υ。 证：设M是G的一个最大对集，U是M非饱和顶点集。由于δ>0且M是最大对集，所以存在|U|条边的一个集E′，它的每条边都和U 的每个顶点相关联。显然，M∪E′是G的边覆盖，因而 β′≤M∪E′=α′+υ?2α′=υ?α′ 即α′+β′≤υ (8.3) 再设L是G的一个最小边覆盖，置H=G[L]，并且设M是H的一个最大对集。用U记H中的M非饱和顶点集。由于M是最大对集，所以H[U]没有连杆，从而 L?M=L\M≥U=υ?2|M| 又因为H是G的子图，所以M也是G的对集，从而 α′+β′≥M+L≥υ (8.4) 综合(8.3)式和(8.4)式，即得α′+β′=υ。?
中科院研究生院图论讲义习题1
第一章习题 1. 对任何简单图G ，(1) 证明：(1) ()2 G υυε?≤；(2) (1) ()2 G υυε?= 当且仅当G K ν?。 2. 证明：(1) ,()m n K mn ε=；(2) 若G 是完全二部图，则2 ()4 G υε≤ 。 3. 图G 有21条边，12个3度顶点，其余顶点的度均为2，求图G 的阶数。 4. 证明：任何简单图必有至少两个顶点具有相等的度。 5. 设G 是简单图，求G 的所有不同的生成子图的个数（包括G 本身和空图）。 6. 证明：任何图中，奇度顶点的个数总是偶数（包括0）。并由此证明：在任一次聚会上握过奇数 次手的人必为偶数个。 7. 证明或反证：如果u 和v 是图G 中仅有的具有奇数度的顶点，则G 包含一条u , v 路。 8. 证明：若4υ≥且1+=νε，则存在)(G V v ∈使得3)(≥v d 。由此证明： n 个球队比赛（4n ≥）， 已赛完n +1场，则必定有一个球队已参加过至少3场比赛。 9. 在一个运动联盟中，将所有运动队组织成两个赛区，每个赛区有13个队，能否恰当安排比赛使 得每个队在其所在赛区中进行9场比赛而与另一个赛区中的运动队进行4场比赛？ 10. 在平面上有n 个点12{,,,}n S x x x =???，其中任两个点之间的距离至少是1。证明在这n 个点中， 距离为1 的点对数不超过3n 。 11. 某次会议有n 人参加，其中有些人互相认识，但每两个互相认识的人，都没有共同的熟人，每 两个互不认识的人都恰好有两个共同的熟人。证明每一个参加者都有同样数目的熟人。 12. 在一个化学实验室里，有n 个药箱，其中每两个不同的药箱恰有一种相同的化学品，而且每种 化学品恰好在两个药箱中出现，问：（1）每个药箱有几种化学品？（2）这n 个药箱中共有几种不同的化学品？ 13. 在一次舞会中，A 、B 两国留学生各(2)n n >人，A 国每个学生都与B 国一些(不是所有)学生跳 过舞，B 国每个学生至少与A 国一个学生跳过舞。证明一定可以找到A 国两个学生12,a a 及B 国两个学生12,b b ，使得1a 和12,b a 和2b 跳过舞，而1a 和22,b a 和1b 没有跳过舞。 14. 证明：2ε δυ ≤ ≤Δ，（其中 2ε υ 称为顶点平均度）。 15. 令G 是至少有两个顶点的图。证明或反证：(1) 删除一个度为()G Δ的顶点不会增加顶点的平均 度；(2) 删除一个度为()G δ的顶点不会减小顶点的平均度。 16. 令G 是一个顶点平均度为2a ε υ = 的无圈图。(1) 证明：G x ?的顶点平均度至少为a 当且仅当 ()2 a d x ≤ 。(2) 利用(1)的结果给出一个算法来证明：如果0a >，则G 有一个最小度大于2a 的 子图。
图论讲义第7章-平面图
第七章 平面图 §7.1 平面图的概念 定义7.1.1 如果图G 能画在曲面S 上，使得任意两边互不交叉，则称G 可嵌入曲面S 。若图G 可嵌入平面，则称G 是可平面图或平面图，画出的无交叉边的图形称为图G 的平面嵌入。 例如，下面是三个平面图及其平面嵌入。 根据定义，下列定理是显然的。 定理7.1.1 若图G 是平面图，则G 的任何子图都是平面图。 定理7.1.2 若图G 是非平面图，则G 的任何母图都是非平面图。 定理7.1.3 若图G 是平面图, 则在G 中添加重边或环边后所得之图仍是平面图。 注：由以上定理知 (1) K n ( n ≤4 ) 和 K 1,n (n ≥ 1)及其所有子图都是平面图。 (2) 环边和重边不影响图的平面性。故以下讨论平面性时总假定图G 是简单图。 定义7.1.2 设图G 是平面图 (已平面嵌入)，G 的边将平面划分出的若干区域都称为图G 的面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数 (割边按两次计)，面R 的次数记为deg (R )。 定理7.1.4 平面图G 中所有面的次数之和等于G 的边数的两倍，即 其中R 1, R 2, … , R r 是G 的所有面。 证明： 对G 的任何一条边e ，若e 是两个面 R i 和 R j 的公共边界，则在计算R i 和 R j 的次数时，e 各提供了1；若e 只是某一个面的边界，则在计算该面的次数时，e 提供了2。可见每条边在计算总次数时，都提供2。因而结论成立。 1 deg()2().r i i R G ε==∑
图论讲义15
定理10.8 (Kuratowski定理)：一个图G是平面图当且仅当G中不包含同态于K5或K3,3的子图。 证明：在10.3节，我们已证明了K5和K3,3不是平面图，再由定理10.4可知，当一个图G包含同态于K5或K3,3的子图，则G不是平面图。从而定理的必要性得证。 现在我们来证明定理的充分性。我们对G的边数归纳证明。当G 只有m=1条边时，显然G是平面图。现在我们假设当G的边数m< N(N≥2)时，G是平面图。现在设G有m=N条边。我们证明：如果G不包含同态于K5和K3,3的子图，但G不是平面图，则导出矛盾。设G不是平面图，则有以下几个结论： (a)G必须是连通的； (b)G不包含割点； (c)如果G中任一边(x, y)被删除，则所得到的图G′中存在包含x和y 的圈。 我们来证明结论(c)。注意到G′是连通的，这因为G不包含割点。如果G′中不存在包含x和y的圈，那么从x到y的每条路径都经过一个公共点z。换句话说，z是G′的一个割点。那么G′可以在z处分解成两个连通分支G1′包含x和z和G2′包含y和z。我们在G1′中加入边xz，得G1"，在G2′中加入边yz的G2"。这时G1"和G2"都不包含同态于K5和K3,3的子图。这是因为G1′是G的子图不可能包含同态于K5或K3,3的子图，假如G1"中包含这样的子图，则该子图必然经过边xz，而在G中可找到一条从z到y的路径P再加上边yx代替xz，从而G中存在同
态于K5或K3,3的子图，这与假设矛盾。同理可证对G2"结论成立。 由归纳假设，G1"和G2"是平面图。根据定理10.5，我们可以找到G1"的平面嵌入，使得xz在外部面上，也可以找到G2"的平面嵌入，使得yz 在外部面上，令G1"和G2"在z处相交，并用xy边取代xz和yz边，则可以得到G的一个平面嵌入，这与G不是平面图的假设矛盾。从而证明了G′不包含割点。即G′是一个块。再由定理3.2，x和y包含在G′ 的一个圈C中，事实上，C可能是包含x和y的若干个圈中的一个。因为G′不包含同态于K5或K3,3的子图，并且G′比G少一条边，由归纳假设，G′是平面图。设G′是G′的平面嵌入。我们选择C为包含x和y且把G′的尽可能多的面包围在其内部的圈。G′的在C的内部的桥称为内部桥，而G′在C外部的桥称为外部桥。我们给C赋予一个顺时针的方向。如果p和q是C上两个顶点，那么S[p,q]表示C上从p到q 顺时针方向的路径的顶点集。S]p,q[=S p,q?{p,q}。注意到，C的任意一个外桥在S[x,y]或S[y, x]上不可能有两个接触点，否则我们可以找到一个圈C′包含x和y且比C包围更多的面到其内部。 G是由平面图G′加上一条边x,y构造起来。考虑到对C的外桥和内桥的要求以及G不是平面图的假设，C一定有一个外桥E和一个内桥I。对于外桥E，E只能有两个接触点i和j，使得 i∈S]x,y并且 j∈S y,x[ I在C上可以有任意多个接触点，但I至少有两个接触点满足：a∈S]x,y并且 b∈S y,x[ 否则(x,y)就可以加入到C的内部，从而得到G的平面嵌入，矛盾。
图论讲义2连通性
第二章 图的连通性 连通图：任二顶点间有路相连。 例 可见在连通图中，连通的程度也是有高有低。 本章的目的就是定义一种参数来度量连通图连通程度的高低。 §2.1 割边、割点与连通度 一、割点： 定义2.1.1 设)(G V v ∈，如果)()(G w v G w >?，则称v 为G 的一个割点。（该定义与某些著作有所不同，主要是在有环边的顶点是否算作割点上有区别）。 例 定理2.1.1 如果点v 是图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得 ][1E G 和][2E G 恰好有一个公共顶点v 。 推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G ?不连通。 以上两个结论的证明留作习题。 定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。 证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。 若0)(=v d ，则1K T ?，显然v 不是割点。 若1)(=v d ，则v T ?是有1)(??v T ν条边的无圈图，故是树。从而)(1)(T w v T w ==?。因此v 不是割点。 以上均与条件矛盾。 充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。路uvw 是T 中一条),(w u 路。因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>?。故v 是割点。证毕。 推论2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。 证明：设T 是G 的生成树，则T 至少有两个叶子u ,v ，由上一定理知，u ,v 都不是T 的割点，即1)()(==?T w u T w 。由于u T ?是图u G ?的生成树，故 )(1)()()(G w T w u T w u G w ===?=?，
图论讲义第1章-图的概念
图论与网络流理论 （Graph Theory and Network Flow Theory） 高随祥 中科院研究生院专业基础课 学时/学分：60/3 本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数理统计各专业的硕士学位研究生作为专业基础课，也可供物理学、化学、天文学、地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、信号等学科专业的硕士研究生选修。主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用。为学习者将来从事有关方面的理论研究打下基础，也为进行应用性研究提供一种有力的工具。
内容提要 第一章 图的基本概念 图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。 路、圈与连通图；最短路问题。 树及其基本性质；生成树；最小生成树。 第二章 图的连通性 割点、割边和块；边连通与点连通；连通度；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。 考核方式：平时成绩＋期末闭卷笔试
图论讲义42H图
§4.3Hamilton图 * 经过图G的每个顶点恰一次的路称为G的Hamilton路。 * 经过图G的每个顶点恰一次的圈称为G的Hamilton圈。 Hamilton图的研究起源于十二面体的游戏（1856） 与Euler图的有效充要条件。 一、必要条件 定理4.3.1 设G G是二部图，若G 是H图，则G 证明： *Herschel 定理 4.3.2若G是 证明：设C是G的 由于C－S是G－S 证毕。 利用定理4.3.2 但定理4.3.2不能来判断下列Petersen图不是H图。
2. 充分条件 （1）度型条件 定理4.3.3(Dirac, 1952) 若G 是简单图，且3≥ν，2 ν δ≥，则G 是Hamilton 图。 证明 用反证法：假定定理不真。令 |{G A =G 的顶点数为3≥ν，2 ν δ≥ ，且G 是非Hamilton 图}。 取A 中边最多的一个G 。因3≥ν，故不是完全图（否则G 是Hamilton 图） 。设u 和v 是G 的不相邻顶点。由G 的选择，G ＋uv 是Hamilton 图。因G 是非Hamilton 图，故G ＋uv 的H 圈必经过e = uv 。于是G 中存在以u 为起点v 为终点的Hamilton 路νv v v L 21。 这里u v =1，v v =ν，令 }|{1E uv v S i i ∈=+和}|{E v v v T i i ∈=。 由于T S v U ?ν，故ν<||T S U ，并且0||=T S I （因为若T S v i I ∈?，则G 将包含H 圈11121v v v v v v v i i +?L L νν，矛盾）。 故ν<+=+=+||||||||)()(T S T S T S v d u d I U ，这与2 ν δ≥的前提矛盾。证毕。 (2) 闭包型条件 定理4.3.4（Bondy & Chvátal,1974） 设G 是简单图，u 和v 是G 中不相邻的顶点，且 ν≥+)()(v d u d ，则G 是Hamilton 图当且仅当G ＋uv 是Hamilton 图。 证明：必要性是显然的。 充分性：若G ＋uv 是Hamilton 图而G 不是，则与定理4.3.3一样可推出矛盾。证毕。 定义：图G 的闭包（closure ）是指由如下方法所得之图： 反复连接G 中度之和不小于ν的不相邻顶点对，直到没有这样的顶点对为止。 图G 的闭包记为C(G)。
图论讲义6染色理论
第六章 染色理论 许多实际问题可以归结为求图的匹配或者独立集。此外，在许多应用中，人们希望知道：一个给定的图，它的边集至少能划分成多少个边不交的匹配？或它的顶点集至少能划分成多少个点不交的独立集？这便是图的边染色和顶点染色问题。 §6.1 点染色 定义6.1.1 设G 是一个无环边的图。G 的顶点正常k 染色(proper vertex k-colouring)π是指k 种颜色k ，，，L 21对于G 的各顶点的一种分配，使得任二相邻的顶点被染上不同的颜色。换句话说，G 的顶点正常k 染色π是一个映射 },,2,1{)(:k G V L →π, 使得)(1 i ?π 是独立集或空集),,2,1(k i L =. 注：设π是G 的一个顶点正常k 染色。令 })(|)({)(V 1i x G V x i i =∈==?ππ，（k i ,,2,1L =）。 则π实际上是对顶点集)(G V 的一种划分：),,,(21k V V V L =π，其中φ=j i V V I ， )(1 G V V k i i ==U ，且每个i V 是独立集或空集),,2,1(k i L =. 例： 定义6.1.2 若存在G 的一种顶点正常k 染色，则称图G 是点k 色可染的(vertex k-colourable)， 有时简称为k 色可染的或可k 染色的。 注：⑴ 每个图G 一定是)(G ν色可染的。 ⑵ 若图G 是k 色可染的，则对任何正整数k m ≥，G 也m 色可染。 定义6.1.3 设G 是无环边的图，令 G k G |min{)(=χ是k 色可染的}， 称)(G χ为G 的点色数，有时简称为色数(chromatic number)。若k G =)(χ，则称G 为k 色图(k-chromatic graph)。
图论讲义41E图
第四章 Euler 图和Hamilton 图 §1. Euler 图 一、基本概念 七桥问题：如下图。从任一陆地点出发，经过每座桥一次且仅一次回到出发点，是否可能？ 哥尼斯堡七桥 G 转化为图论问题：图G 中从任一顶点出发，经过每条边恰好一次回到出发点，是否可能？ Euler 环游(tour,circuit,closed trail)：经过图G 的每条边恰好一次的闭迹。 Euler 迹（trail ）：经过每条边恰好一次的迹。 Euler 图：有Euler 环游的图。 七桥问题：图G 是否Euler 图？ 二、Euler 图的判定 定理4.1.1 一个非空连通图是Euler 图当且仅当它没有奇度顶点。 证明 必要性：设图G 是Euler 图，C 是G 中一个Euler 环游。对)(G V v ∈?，v 必在C 上出现。因C 每经过v 一次，就有两条与v 关联的边被使用。设C 经过v 共k 次，则k v d 2)(=。 充分性：无妨设1)(>G ν。因G 连通，故至少有一条边。下面用反证法证明充分性结论。 假设图G 无奇度顶点，但它不是Euler 图。令 S ={G|G 至少有一条边，无奇度顶点，且不是Euler 图} 则φ≠S 。取S 中边数最少的一个，记为G ′。因2)(≥′G δ，故G ′含有圈，因而含有闭迹。设C 是G ′中一条最长的闭迹。由假设，C 不是G ′的Euler 环游。因此)(\C E G ′必有一个连通分支至少含有一条边。记这个连通分支为0G 。由于C 是闭迹，故0G 中没有奇度顶点，且)()(0G G ′<εε。由G ′的选择可知，0G 必有Euler 环游0C 。由于G ′连通，故C 必经过0G 中至少一个顶点，从而φ≠)()(0C V C V I 。因此0C C +是G ′的一条闭迹，且 )()(0C C C εε>+，这与C 的选取矛盾。证毕。
图论讲义第5章-支配集
第五章 支配集、独立集、覆盖集和 Ramsey 数
本章讨论图中具有某种特性的顶点子集和边子集，以及它们之间的关系。本章所讨论的 图均为简单图。
§5.1 支配集、点独立集、点覆盖集
一、支配集(Domination set)
定义 5.1.1 设 D ? V (G ) ，若对 ?u ∈ V (G ) ，要么 u ∈ D ，要么 u 与 D 中的某些顶点相邻， 则称 D 为图 G 的一个支配集。如果一个支配集的任何真子集都不是支配集，则称它为极小支 配集。 G 的含顶点最少的支配集称为最小支配集。 图 最小支配集的顶点个数称为 G 的支配数， 记为 γ (G ) 或 γ 。 例如，在下图中， D0 = {v0 } ， D1 = {v1 , v 4 , v7 } ， D2 = {v1 , v3 , v5 , v6 } 都是 G 的支配集， 前两个是极小支配集， D0 是最小支配集。 γ (G ) = 1 。 v1 v8 v7 v6 G v5 v0 v2 v3 v4
注： （1）最小支配集必是一个极小支配集，反之不然。 （2）任一支配集必含有一个极小支配集。 （3）极小支配集不唯一，最小支配集一般也不唯一。 （4）对二部图 G = ( X , Y ) ，X 和 Y 都是支配集。 （5）若图 G 有完美匹配 M*，则从 M*中每边取一个端点构成的顶点集是一个支配集。 定理 5.1.1 设图 G 中无孤立顶点，则存在支配集 D，使得 D = V (G ) ? D 也是一个支配集。 证明：无妨设 G 是连通图。于是 G 有生成树 T。任取 v0 ∈ V (G ) 。令
D = {v | v ∈ V (G ) 且 d T ( v0 , v ) ＝偶数}，
则 D = V (G ) ? D = {v | v ∈ V (G ) 且 d T ( v0 , v ) ＝奇数}，且 D 和 D 都是支配集。证毕。 定理 5.1.2 设图 G 无孤立顶点， D1 是一个极小支配集，则 D1 = V (G ) ? D1 也是一个支配集。 证明（反证法） ：若不然，存在 v0 ∈ D1 ，它与 D1 中所有顶点都无边相连，但它又不是孤立顶 点，故必与 D1 中顶点连边，因此 D1 ? v0 仍是支配集。这与 D1 是极小支配集矛盾。证毕。 推论 5.1.1 设图 G 中无孤立顶点。 G 的任一个极小支配集 D1 ， 对 必存在另一个极小支配集 D2 ， 使得 D1 ∩ D2 = φ 。 证明：由定理 5.1.2， D1 = V (G ) ? D1 也是一个支配集，且 D1 ∩ D = φ 。 D1 中必含有一个极 小支配集 D2 。显然 D1 ∩ D2 = φ 。证毕。
1