图和子图 图和简单图
图 G = (V, E)， 其中 V = {} V ---顶点集， ---顶点数 E = {e1,e2,......,e}E ---边集， ---边数 例。 左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G的几何实现（代表）， 它们有无穷多个。真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。不过今后对两者将经常不加以区别。
称 边 ad 与顶点 a (及d) 相关联。也称 顶点 b(及 f) 与边 bf 相关联。
称顶点a与e 相邻。称有公共端点的一些边彼此相邻，例如p与af 。
环（loop，selfloop）：如边 l。 棱（link）：如边ae。 重边：如边p及边q。 简单图：（simple graph）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。 一条边的端点：它的两个顶点。
(G)E(G).。 记号：(G)V(G),
习题
apqbcrdefG = (V, E)
1.1.1 若G为简单图，则 。
21.1.2 n ( 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。
同构
在下图中， 图G恒等于图H , 记为 G = H VG)=V(H), E(G)=E(H)。 图G同构于图F V(G)与V(F), E(G)与E(F)之间 各 存在一一对应关系，且这二对应关系保持关联关系。 记为 G F。
注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。
x adbwcxadbwca’x’d’b’w’c’eyz G=(V, E)
ez y H=(V’, E’)y’e’z’F=(V’’, E’’)
1
注 判定两个图是否同构是NP-hard问题。 完全图(complete graph) Kn
空图（empty g.） E = 。
V’ ( V) 为集 V’中任二顶点都互不相邻。
二部图（偶图，bipartite g.） G = (X, Y ; E) 存在 V(G) 的一个 2-划分 (X, Y), 使X与Y 都是集。
完全二部图 Km,n 二部图G = (X, Y)，其中X和Y之间的每对顶点都相邻，且 X = m, Y = n 。
K1K2K3K4K5类似地可定义，完全三部图（例如 Km,n,p），完全 n-部 图等。
例。用标号法判定二部图。 习题
二部图
K3,3K1,5K2,2,2
1.2.1 G H (G) = (H) , (G) = (H) 。 并证明其逆命题不成立。
1..2.2 证明下面两个图不同构：
1.2.3 证明下面两个图是同构的：
1.2.4 证明两个简单图G 和H同构 存在一一映射 f : V(G) V(H) ，使得 uv E(G)当且仅当
f(u)f(v) E(H) 。
1.2.5 证明：(a).(Km,n ) = mn ;
(b). 对简单二部图有 2/4 .
1.2.6 记Tm,n为这样的一个完全m-部图：其顶点数为n，每个部分的顶点数为[n/m]或{n/m}个。证明：
nkk1 (a). (Tm,n) = (m1) 其中 k =[n/m] .
22 (b)*. 对任意的n顶点完全m-部图G，一定有 (G) (Tm,n)，且仅当G Tm,n时等式才成立。
1.2.7 所谓k-方体是这样的图：其顶点是由0与1组成的有序k-元组，其二顶点相邻当且仅当它们恰有一个坐标不同。证明k-方体有个顶点，k*2 k-1条边，且是一偶图。
1.2.8 简单图G的补图G c 是指和G有相同顶点集V的一个简单图，在G c中两个顶点相邻当且仅当它们在G不相邻。
(a). 画出Kcn和 Kcm,n。
(b). 如果G G c则称简单图G为自补的。证明：若G是自补的，则 0, 1 (mod 4)
2
关联矩阵M(G)与邻接矩阵A(G)
M(G)=[mi,j], A(G)=[ai,j] ,
其中 mi,j = 顶点vi与边ej 的关联次数= 0, 1, 2. ai,j = 连接顶点vi 与 vj 的边数 。 例。
e111M(G)00
e21100e30110e40011e51001e60002e71v10v21v30v4v1e5e6v4e1e2e7e4G = (V, E)v2e3v3
v102A(G)11
v22010v31101v41v10v2
1v31v4 子图
子图(subgraph) H G V(H) V(G) , E(H) E(G) 。 真子图 H G。 母图（super graph）。
生成子图（spanning subg.） H G 且V(H) = V(G) 。 生成母图。
基础简单图 （underlying simple g.）。
导出子图（induced subg.）G[V’], (非空V’ V ) 以V’为顶点集，以G中两端都在V’上的边全体为边集构成的G的子图。 边导出子图 G[E’] 非空E’ E 以E’为边集，以E’中所有边的端点为顶点集的的子图。 例。
ueydxfghcwG[{u,w,x,y}]G[{u,w,x}]avbG[{f, c]}G[{c, d, e}]
以上两种子图，其实，对应于取子图的两种基本运算。下面是取子图的另两种基本运算： G - V’ 去掉V’及与V’相关联的一切边所得的剩余子图。
3
G=(V, E)
即 G[V \\ V’]
G - E’ 从中去掉E’ 后所得的生成子图
例。G - {b, d, g}, ( = G[E \\ {b, d, g}] ) G - {b, c, d, g}, ( G[E \\ {b, c, d, g}] ) G - {a, e, f, g}. ( G[E \\ {a, e, f, g}] )
注意 G[E \\ E’] 与G - E’ 虽有相同的边集，但两者不一定相等 ： 后者一定是生成子图，而前者则不然。
上述四种运算是最基本取子图运算，今后老要遇到，一定要认真掌握好。关于子图的一些定义还有： G + E’ 往G上加新边集E’ 所得的（G的母）图。 为简单计，今后将 G {e} 简计为 G e ； G - {v} 简计为 G - v 。 设 G1, G2 G ，称G1与G2为 不相交的（disjiont） V(G1) V(G2) = ( E(G1) E(G2) = )
边不相交 （edge-distjiont） E(G1) E(G2 ) = 。 ( 但这时G1与G2仍可能为相交的）。 并图 G1G2 , 当不相交时可简记为 G1+G2. 交图 G1G2 .
习题
1.4.1 证明：完全图的每个导出子图是完全图；偶图的每个导出子图是偶图。
1.4.2 设G为一 完全图，1 n -1。证明：若 4，且G中每个n顶点的导出子图均有相同的边数，则 G K或 Kc 。
顶点的度
顶点 v的 度 dG(v) = G中与顶点v 相关联边数。 （每一环记为2） 最大、最小度 ， 。 （(G) , (G) ) 定理1.1 (hand shaking lemma) 任一图中，
d(v)2
vV.
系1.1 任一 图中，度为奇数顶点的个数为偶数。
例。任一多面体中，边数为奇数的外表面的数目为偶数。 证明。作一图，使其顶点对应于多面体的面，并使其中二顶点相邻当且仅当对应的两个面相邻。......
k-正则图 （k-regular g.) d(v) = k, v V . 习题
0-正则图1-正则图2-正则图
1.5.1 证明： 2/ 。
1.5.2 若 k-正则偶图(k > 0)的2-划分为 (X, Y),则
X = Y。
1.5.3 在人数 >1的人群中，总有二人在该人群中有相同的朋友数。
1.5.4 设V(G) = {v1,v2,......,v}，则称 ( d(v1), d(v2), ...... , d(v) ) 为G的度序列。证明：非负
4
3-正则图
整数序列 ( d1 ,d 2, ......, d n) 为某一图的度序列
di1ni是偶数。
1.5.5 证明：任一 无环图G都包含一 偶生成子图H，使得 dH(v) dG(v)/2 对所有v V 成立。 1.5.6* 设平面上有n个点，其中任二点间的距离 1，证明：最多有 3n对点的 距离 = 1 。
路和连通性
途径 （walk) 例如 （u，x）-途径
W = ueyfvgyhwbvgydxdydx (有限非空序列） = uyvywvyxyx (简写法---当不引起混淆时） 起点（origin ） u 。 终点（terminus） x。 u内部顶点（internal vertex） y, v, w, x。
ea （注意，中间出现的x也叫内部顶点。）
yfv长 边数（重复计算）。
g节（段，section）。 例如W的(y, w)-节=yvw 。
dhbW-1
（逆途径）, WW’（两条途径W与W’相衔接）。 迹( trail) 边各不相同的途径。 例如，yvwyx 。 xcw路 (path) 顶点各不相同的途径。（可当作一个图或子
图)。例如， yvwx 。
d(u, v) = u与v之间最短路的长。 例。（命题）G中存在(u, v)-途径 G中存在(u, v)-路。
G中顶点u与v为连通的(connected) G中存在(u, v)-路
( G中存在(u, v)-途径。)
V上的连通性是V上的等价关系，它将V划分为（等图 G价类）：
V1,......,V
使每个Vi中的任二顶点u及v都连通（即存在(u, v)-路）。 称每个 G[Vi] i=1,2,......
为G的一个分支（component）; 称(G）为G的分支数。 G为连通图 (G) = 1
G中任两点间都有一 条路相连。 G为非连通图 (G) 1。
记号 对任一非空 SV ，令 S = V\\S, 记（称为边割）
[S, S] = G中 一 端在S中，另一 端在S中 的一切边的集合。 例。（命题）G连通 对任 S V 都有 [S, S] 例。（命题） 简单图G中， k G中有 长 k 的路。
习题
1.6.1 证明：G中长k为的(v)-途径的数目, 就是A k
i ,vj 中的(I, j)元素。 1.6.2 证明：对简单图G有， 12 G连通。
5
对于 > 1，试给出1的不连通简单图。 21.6.3 简单图G中， > [/2] - 1 G连通。 当是偶数时，试给出一个不连通的([/2]-1)
正则简单图。
c
1.6.4 G不连通 G 连通。
1.6.5 对任意图G的任一边e，有 (G) (G-e) (G) +1 。
1.6.6 G连通，且 d(v)=偶数， v V (G-v) d(v)/2, v V. 1.6.7 连通图中，任二最长路必有公共顶点。
1.6.8 对任一图的任三个顶点 u, v, w 都有 d(u, v)+d(v, w) d(u, w)。
1.6.9 任一简单图非完全图中，一定有三个顶点 u, v, w， 使得uv, vw E 而 uw E。
圈
闭途径（closed walk) 起点=终点且长 0 的途径。 闭迹 (closed trail) 边各不相同的闭途径。
圈（cycle） 顶点各不相同的闭迹。 （可当作一图或子图。）
例。闭途径： uyvyu ; uywxywvu ； uyuyu。
u 闭迹：uyxwyvu。
ea 圈： yfvgy ; uywvu。
f yvgk-圈（k-cycle） 长为k的圈。
d例。1-圈（即一条环）， 2-圈(由重边组成），3-圈（又称hb三角形）。
奇圈 (odd cycle)。 xcw 偶圈 (even cycle)。
定理1.2 G 为二部图 G不含奇圈。 证明：：设G的2-划分为（X, Y），由G的定义，G的任一圈中，X和Y的顶点一定交错出现，从而其长必为偶数。
：不妨设G为 连通的。 任取一顶点u,令 X = { xV d(u, x) = 偶数 }, Y = { yV d(u, y) = 奇数}。 由于，易见，(X, Y)为V的
v2-划分，只要再证X和Y都是G
的集（ 即X（或 Y）中任二Pu’P’uw顶点v， w都不相邻 ）即可： 令
Q’P与Q分别为最短(u, v)-路与最Q 短(u, w)-路。设u’为P与Q的
最后一个公共顶点； 而 P’与Q’分别为P的(u’, v)-节与Q的(u’, w)-节。则P’与Q’只有一公共顶点。 又，由于P与Q的(u, u’)-节的长相等， P’与Q’的长有相同的奇偶性，因此v与w不能相邻，不然，
v( P’)-1 Q’wv 将是一 奇圈，矛盾。 例。（命题） 图G中 2 G中含圈。 例。（命题） 简单图G， 2 G含长 +1 的圈。 例。（命题） 任一图中
(a). 含圈。
(b)*. + 4 含二条边不重的圈。
6
习题
1.7.1 若边e在G的一闭迹中，则e在G的一圈中。 1.7.2 证明：(a). G含圈。
(b)*. + 4 G含两个边不重的圈。
最短路问题
赋权图（weighted g.)(权 1 之推广 ) 权( weight ) w(e) 0. w(H) =
H G .
ew(e), E(H) 路P的长 = w(P)
顶点u与v距离 d(u, v) = 最短(u, v)-路的长。 问题 求最短( u0, v0)-路。
转 求最短(u0, v)-路, v V \\ {u0}. 简化 只考虑简单图，且w(e) > 0 e E.
（ w(uv) = 0 时， 可合并u与v为一 顶点）。 原理 逐步求出顶点序列 u1, u2, ............
使 d(u 0, u1) d(u 0, u2) ...... 记 S0 = { u0 },
Sk = { u 0, u1,.............,u k} ， Sk= V \\ S 。 Pi为最短( u0, ui)-路 i= 1, 2,......
(1).u1 ： u1是使 w(u 0u1) = min{ w(u 0v) v u 0 } 者 . 得 S1 = S0{u1} , P1 = u 0u1 .
(2). 若已求得S k-1 ; d(u 0, u1),.........d(u 0, u k-1) ; 及最短 (u 0, u i)路 Pi i=1.2,...,k-1 .
u k ：显然，
d(u0, u k) = min{ d( u0, v) v Sk1} = d(u 0, u j ) + w( u ju k ) 某 j{ 1,2,......,k-1 } = min{ d( uo, u ) + w( uu k ) u S k-1 }
= min{d( u 0 , u ) + w(uv ) v Sk1 , u S k-1 } = min { l( v ) v Sk1}
其中， l( v ) = min { d( u o, u ) + w( uv ) u S k-1} ( l( u k ) = d( u 0 , u k ) ) S k = S k-1 { u k } ,
P k = P j u ju k 某 j{ 1,2,......,k-1 } 。 update 进行下一 步时，只要更新 l( v ) 即可：
l( v ) min { l( v ) , l( u k ) + w( u kv ) } v Sk
Dijkstra算法
(1).作为开始：l( u 0 ) 0 ; l( v ) v u 0 ; S0 { u 0 }; k 0 . (2). （这时已有Sk = { u 0, u1,.............,u k}）
l( v ) min { l( v ) , l( u k ) + w( u kv ) } v Sk 再计算 min { l( v ) }，设其最小值点为 u k+1 ，令 S k+1 = S k { u k+1 }。
7
(3). 若 k = - 1 , 仃止；不然，令 k k+1 ,并回到 (2) 。
S k-1u ju ku 0S kvS k-178u0 223142373465146计算复杂性
加法： (- 1)/2 比较： (- 1)/2 2
2
v S： (-1)
+)________________________________________________ 共 O (2 )
凡是复杂性为 p( , ) 的算法 ( p( . , . ) 为一多项式 ) 称为“好算法”( “good algorithm”------J.Edmonds )。这是相对于指数型算法而言的：在10 - 6秒/步运算速度下：
n= 10 20 30 40 50 复杂性
n3 .001sec .008sec .027sec .0sec .125sec n5 .1sec 3.2sec 24.3sec 1.7min 5.2min n2 .001sec 1.0sec 17.9min 12.7days 35.7years 由上表可见，两种算法有天壤之别。
注 1.若只关心求d(u 0 , v 0)则算法进行到v 0 S k时停止。
2.计算过程中，所得子图是一 棵树。每步都是往其上增加一条边及一个顶点，因此该过程称为 tree growing procedure 。
3.若要计录u 0到每个顶点u的最短路，只要记录下该路中u 的前一 个顶点即可。
习题
1.8.1 描述一个算法以确定 (a). 一图的各个分支；
(b). 一图的围长（即最短圈的长）。 并说明你的算法好到什么程度。
树 树
无圈图（acyclic g.；林forest）。 树（tree） 连通无圈图。
叶 (leave) 树中度为1的顶点。
定理2.1 树中任二顶点间有唯一的路相连。
证明：反证，假设存在树G，其中有二顶点u与v，其间有二不同(u, v)-路P1 和P2 相连。因P1 P2 ，一定存在P1 的一条边e = xy ，它不是P2 的边。显然，图 P1 P2 - e是连通的，从而其中包含一条(x, y)-路P。于是P + e 是G中的一 圈，这与G为无圈图相矛盾。
注意 (1). 当G无环时，易见，
G是树 G中任二顶点间有唯一的路相连。 (2). 以下结论不一 定成立： 闭途径 圈 。
8
定理2.2 G是树 = - 1。
证明：对 进行归纳。当 = 1时，G = K 1 ，成立。假设定理对 小于 个顶点的树成立，而G为 个顶点的树。任取G的一边uv 。它是G中的一条路，由定理2.1知， G - uv 不连通，且 它恰有二分支（习题1.6.5），设为G 1与G 2 。它们都是连通无圈图，因此是树。又，它们的顶点数都小于 。由归纳假设知
(G I ) = (G I )- 1 I= 1,2 . 故， (G) = (G 1 ) + (G 2 ) + 1 = (G 1 ) + (G 2 ) - 1 = (G) - 1 。
推论2.2 每棵非平凡树至少有两个度为1的顶点。 证明：由于G为非平凡连通图， d(v) 1 , v V 。 再由定理1.1 及2.2知，
d(v)222 ，
vV由此知推论成立。 例。（命题）恰只包含二度为一顶点的树是路。
习题
2.1.1 证明：非平凡树中，任一最长路的起点和终点均是度为 1的顶点。再由此去证明推论2.2。 2.1.2 当 = - 1 时，证明以下三结论是等价的： (a) G 是连通图； (b) G是无圈图； (c) G是树。
2.1.3 一树中若 k，则其中至少有k个度为 1 的顶点。 2.1.4 G为 林 = - 。
2.1.5 若林G 恰有2k个奇点，则G中存在k条边不重的路P1 ,P2 ,..,Pk ,使得 E(G) = E(P1 )E(P2 ) ... E(Pk )。
2.1.6 正整数序列(d 1 ,d 2 ,...,d )是一 棵树的度序列，当且仅当
di1i2(1)。
2.1.7 饱和烃分子形如C mH n ,其中碳原子的价键为4，氢原子的价键为 1，且任何价键序列都不构成圈。证明：对每个m，仅当n = 2m + 2时C mH n方能存在。
割边和键
e为割边( cut edge) (G-e) > (G) 。
（即 (G-e) = (G) + 1 ） 定理2.3 e为G的割边 e不在G的任一圈中 。
证明：令 e = xy ，则 x 与 y在G的同一分支中。于是， e 为G的割边
(G-e) = (G) + 1
x与y不G-e在同一分支中 G-e中无(x,y)-路
G中无含e的圈。
定理2.4 图G连通，且每边是割边 G为树。
9
证明：注意到以下事实即可，
G无圈 G中每边不在任一圈中
G中每边是其割边。
连通图G的生成树（spanning tree ) G的生成子图，且为树。 推论2.4.1 每一连通图都包含一生成树。 证明：令 T 为极小( minimal)连通生成子图 （意指 T 的任一真子图都不是连通生成子图）（由定义，T 可在保持连通性的前提下，用逐步从G中去边（ 所去的边一定在一圈中（即非割边））（每次破坏一圈）的办法求出。
由T的定义知， (T) = 1 ，
(T - e) = 2 e E(T) 。
即 T 的每边为割边，故由定理2.4知T为树。
注 也可用极大无圈（生成）子图（即其真生成母图都含圈）来求生成树 T。它可由V上的空图开始，在保持无圈的前提下，逐步由G中取边的办法求出。 （为何是生成树？）
推论2.4.2 G - 1 。
定理2.4.5 设 T 为G的一生成树，e为G中不属于T的边，则T+e 含唯一的圈。 证明： 由于T 无圈，T + e 中的每个圈都包含e 。又，
C为 T + e 的一圈 C - e 为T 中连接e的两个端点的路。 但，由定理2.1知，T中恰只有一条这样的路，因此 T + e中包含唯一的圈。
小结 G为树
G中任二顶点间有唯一的路相连，且无环 G连通，无圈
G连通，且每边为割边 G连通，且 = - 1 G连通。且 = - 1 。
图G的边割（ edge cut） [S,S] S V
G中一端在S另一端在S中的 边的子集合。 显然，在连通图G中，
E’ 边割 (G-E’) > 1 。 键（bond, 割集cut set ) 极小非空边割。
例。e是G的割边 {e} 是G的键。 例。左图G中，
{uv, zv, zy, vw, yx},
uvw {zu, zv, zy, xy, xw}, {uv, zv, zy} {zu, zv, zy}
都是边割，其中后两个为键。而 E’ ={zu, zv, zy, uv}不是G的边割，当然更不是G的键，虽然G- E’ 变成不连
zyx通。
易见，当G连通且 S 时，
边子集B 为G的键 B是使G不连通的E的极小子集。
(G-B)=2，且中每边的两端点分别在二分支中。 边割B = [S,S]为键 G[S],G[S]都连通。 （习题）
设H为G的子图，称子图 G - E(H) 为G中H的补图，记为：
10
H(G) 。
特别地，当T为G的生成树时，称 T 为G的余树。
定理2.6 设T为连通图G的一个生成树， e为T的一条边，则
(1).余树T 不包含G的键；
(2). T + e中唯一包含的G的一个键。
GTT
证明：(1).因 G - E(T )= T 连通，则T不包含G的边割，从而也不包含G的键。 (2).注意到e为的T割边，令S与S 分别为 T - e的二分支的顶点集。考虑 B = [S,S]G
由于G[S] ( 包含T-e的一个分支T[S]) 与G[S] ( 包含T-e的一个分支T[S]) 都连通，B必是G键，包含于T+e中。
来证B为包含在T+e中的唯一键,只要再证对包含在T+e中的G的任一键B’，一定有 B = B’ 即可： 假设不然，由于键的极小性，B’不会包含B，从而一定存在B的一边b B’ 。于是
G - B’ T - e +b ( 注意到 B’ T+e G-B’ T-e ) 但T-e+b也是G的一生成树（因其边数= -1，且连通），从而G - B’ 连通，这与B’ 为G的键相矛盾。
附录 设G连通，T为其任一生成树。
对每一 e T ，T+e 中有唯一圈C，因而可得 C1 ,C2 ,......,C-+1
共 - + 1个 不同的圈 ，每个称为G的一个基本圈。 同样，对每一 e T ，T+e中有唯一的键因而可得 B1 ,B2 ,......,B-1
共 - 1个不同的键，每个称为的一个基本割集。
设S1 ,S2为二集合，记其对称差( 即（S1S2）-（S1S2） )为 S1 S2
称为它们的环和(ring sum)。 性质
1) 图G的每一边割是G的一些割集的边不重并。
2) 设B1 ,B2 为图的任二边割，则B1 B2 也是G的边割。 （对任二非空V1 ,V2 V， 有
[V1 ,V1][V,V] = [V2 , V2], 其中V3 =(V1 V2)(V1 V2 ) ）。 3) 设边子集E’与E”分别为G中一些圈的边不重并，则E’E” 亦然。 4) G的每个圈可唯一地表为G的一些基本圈的环和。 5) G的每个边割可唯一地表为G的一些基本割集的环和。 6) 边子集E’为G中一些边不重圈的并集 边子集E’与G中每个边割有偶数条公共边。 7) 边子集B为G的一个边割 边子集B与G的每个圈有偶数条公共边。
8) G为一些圈的边不重并 d(v) = 偶数 v V
习题
2.2.1 设G连通且 e E，证明：
(a) e在G的每棵生成树中当且仅当e是G的边割。 (b) e不在G的任一生成树中当且仅当e是G的环。
2.2.2 无环图G恰只有一棵生成树T，则G = T 。 2.2.3 设F是G的极大（maximal）林，证明： (a) 对G的每个分支H， FH 是H的生成树；
11
(b) (F) = (G)- (G)。
2.2.4 证明： 任一图G至少包含 - + 个不同的圈。 2.2.5 (a) 若G的每个顶点均为偶点（即，度为偶数的顶点），则G没有割边； (b) 若G是k-正则偶图且 k 2，则没有割边。 2.2.6 当G连通且 S 时，
边割B = [S,S]为键 G[S],G[S]都连通。 2.2.7 图G的每一边割是G的一些键（即，割集）的边不重并。 2.2.8 在图G中，设B1和B2为键，C1和C2为圈（看作边子集）。证明： (a) B1B2 是G的键的边不重并集； (b) C1C2是G的圈的边不重并集；
(c) 对G的任一边e，(B1B2)\\{e}都包含键； (d) 对G的任一边e，(C1C2)\\{e}都包含圈。
2.2.9 证明：若图G包含k棵边不重的生成树，则对于顶点集每一划分(V1 ,V2 ,...,Vn )，端点在这个划分的不同部分的边的数目至少为 k(n-1)。
割点
称顶点v为G的割点(cut vertex) E可划分为二非空子集E1及E2，使G[E1]与G[E2]只有一公共顶点v。
显然， 当G无环时，
v为割点 (G-v) > (G) 。
存在二顶点x及y ，使G中任一(x, y)-路一定包含v。
E1E2 G
例。（边割）v, v 为G的键 v不是的G的割点。
定理2.7 在树G中
v为割点 d(v) > 1 。
证明：(i) 若d(v) = 0，则G K1 ，v不是割点。
(ii) 若 d(v) = 1，则G -v 仍然是树。因此 (G-v)= 1 = (G)，从而 v不是割点。 (iii) 若 d(v) > 1，则G中存在与v相邻接的二不同顶点u, w 。由定理2.1知，uvw是G中的唯一(u, w)-路，因此G-v中不含(u, w)-路，（即G-v中u,w不连通）
(G-v) > 1 ， 即v为G的割点。
推论2.7 非平凡、无环、连通图中，至少有二顶点不是割点。 证明：令T为G的一生成树，由推论2.2及定理2.7知，T中至少存在二顶点 u与v不是T的割点，则它们也不是G的割点：这是因为对于u (及v)有
1 = (T-u) (G-u) 1 ， ∴ (G-u) = 1 =(G) 。 习题
2.3.1 设G为 3的连通图，证明：
(a) 若G有割边，则G有顶点v使 (G-v) > (G)； （即，割边必有一端点为割点） (b) (a)的逆命题不成立。
12
2.3.2 证明：恰有二顶点为非割点的简单连通图必是一条路。 2.3.3 在简单连通图G中证明：
v为G的割点 G的任一生成树不以v为叶。
生成树的计数及Caley公式
本节只讨论无环连通图。
将图G的关联A 矩阵中每列的两个1元素之一改为 -1，得一新矩阵，记为Aa（它是G的一个定向图的关联矩阵）。例如：
e1v11Aav20v30v41 e21100e30110e40011e501 01v1e1e2e5v2e3记A为从Aa中删去某一行所得的( -1) 矩阵。 v4e4v3 引理1 设A 1 为A的任一(-1) 阶子方阵，则
det(A1 ) = 1 A1 的列对应于G的一生成树。
证明：令划去的行对应于顶点u，记H为以全体与A1的列相对应的边构成的生成子图。由于 (H)= -1 ,因此有
H连通 H为G的生成树。
（1） 当H不是G的生成树时，由上述知，H不连通。令S为H中不含u的一个分支的顶点集。易见，A1中对应于S的全体行向量之和为一零向量。因此，det(A1 ) = 0。
（2）当H是G的生成树时，重排A1 的行、列如下：
取H的一个度为1的顶点u1 ，并使 u1 u 。记 u1 在H中的关联边为e1 ; 再取 H-u1
中的一个度为1的顶点u2 ，并使 u2 u ,记 u2 在H-u1 中的关联边为 e2 ;......。
按u1 ,u2 ,...及e1 ,e2 ,,,,,,,的顺序重排A1 的行、列，得矩阵A1’ 。易见，A’1 为下三角型。且主对角线元素全为 1 ,因此 detA1 = detA1’ =1 。
Binet-Cauchy定理 设矩阵 P=[ pij ]mn ， Q=[ qij ]nm ，且m n 则
det(PQ)1j1...jmnpij1...pmj1.........p1jmqj11......pmjmqjm1.........qj1m... qjmm
T
引理2 连通图的生成树数目 = det（AA）。 证明：由Binet-Cauchy定理知，
T2
det(AA) = ∑(detA1) (对A的所有 v-1阶子方阵A1求和） 但由引理1知
detA1 = 10A1的列对应于G的一生成树其它
得证。
无环图G的度矩阵
K = [ kij ] ， 其中
ijkijd(vi)当ij且vi与vj间有ij条平行边
当ij13
例如对本节开头的例子有
v1e1e2e5e4v2e3v3
定理 连通图G的生成树数目 = K的任一元素的代数余子式
T
证明：容易验证，K=AaAa 。 又，K的任一行（列）的元素的代数和 = 0，因此 K的所有代数余子式都相等。 再，设A k为从A a中去掉第k行所得的 (-1) 矩阵，易见，
T
A kA k = 从K中去掉第k行第k列后所得的子方阵 故由引理2知本定理成立。
例。前例的图的生成树数目 = K的(2,3)-元素的代数余子式
v4v12K101v21311v30121v41v11v2 1v33v42
=(1)2311111 = 8 。 301
n-2
定理（Cayley） K n 有 n个不同的生成树。 证明：用上述定理可直接证出（习题）。
习题
2.4.1 求Ｋ３，３的生成树数目。
n-3
2.4.2 若ｅ是Ｋｎ的一条边， 则 Ｋｎ－ｅ的生成树数目为 (n-2)n 。
连线问题
问题 设城市vi与vj间建立直接通信线路的费用为cij（ 0）。 建设连接 {v1,v2,......,v}的通讯网使造价最省
在赋权图G中求一最小权连通生成子图； 在赋权图G中求一最小权生成树（最优树）。
下面的Kruskal算法是在非赋权图中求生成树的“极大无圈子图”算法的改进，它是一种贪心算法（greedy algorithm）：
Kruskal’s algorithm
(1) 选棱（link）e1 使w(e1)最小；
(2) 若已选定 e1 ,e2 ,...,ei ，则从 E\\{e1 ,e2 ,...,ei}中选取 ei+1 使 (i) G[{e1 ,e2 ,...,ei } {ei+1 }]无圈； (ii) w(ei+1)是满足(i)之最小者。
(3) 若(2)不能再进行下去时，停止。 否则，回到 (2)。
定理2.10 Kruskal算法求出的生成树 = G[{e1 ,e2 ,...,e-1 }] 是最优树。
*
证明：反证，假设T 不是G的最优树。取G的一最优树T。令ek为{e1 ,e2 ,...,e-1 }中（ 按顺序）第一个不属于T的边，且令T为最优树中使k为最大者。则T+ek中唯一的圈C包含ek ，且C中
**
必含一条边e’k T (不然，C T，矛盾。）但
T’ = T + ek -e’k
14
也是G的生成树。（因e’k不是T + ek的割边（定理2。3），从而T’ 连通，且其边数= -1。）又，由于T的子图
G[{e1 ,e2 ,...,ek-1 } {e’k }] 也不含圈，由法算法知
w(ek ) w(e’k) ∴ w(T’) w(T)，
即T’也是G的最优树，且{e1 ,e2 ,...,e-1 }中第一个不属于T’的边的下标 > k。这与k的取法相矛盾。
实现 先按权的不减顺序将边集重排成 a1 ,a2 ,...,a 。
关于算法中无圈性的判定，我们有一简单的办法： 当S={e1 ,e2 ,...,ei }已取定时，对候选边aj G[S {aj}] 无圈 aj的两端点在林G[S]（此处当作生成子图）的 不同分支中。
从而我们有求最优树的标记法：
开始：取a1为候选边； 并将vk标以k， k = 1,2,..., 。
若S={e1 ,e2 ,...,ei }已取定，当候选边aj 的两端点有相同标号时，改取aj+1为 候选边（丢掉aj 永不再考虑）；否则选定ei+1=aj ，并将G[S]中aj两端点所在的二分支的顶点重新标号，标以两者中的最小者。
算法复杂性
边排序 O( log2 ) 6例 比较边两端的标号
66 重新标号 O(( -1) ) 323
故为好算法（ O( ) ）。
72 3438
附录 1 （A） Prim’s algorithm （也是一种贪心算法） T , V’ {u}
for all vV’ do L(v) w(uv) //initializing L(.); V’=V\\V’ while V’V do begin
find vertex w s.t. L(w)=min{ L(v) v V’ } and denote the associated edge from V’ to w by e T T {e}, V’ V’ {w}
for all vV’ do //updating L(v) from new vertex w L(v) if w(vw) < L(v) then w(vv) end
2
Prim算法的复杂性为 O()
（B）Steiner tree prob.： （NP-hard prob.)
已给赋权连通图G中，任给定 V’ V ，求一最小权树 T 使 V(T) V’ 。
习题
2.5.1 用Kruskal算法解带约束的连线问题：用最小费用建立一连接若干城市的网络。但某些特定的城市对间要求有直通线路相连。
2.5.2 连通图G的树图是这样的一个图：其顶点集是G的全体生成树{T1 ,T2 ,...,T}，且 Ti和Tj相连 它们恰有 v-2条公共边。 证明：任何连通图的树图是连通的。
15
连通度问题 连通度
B E(G)为图G的k-边割 B = k 。
图G的边连通度（edge connectivity)
'(G)min{E' E'为G的边割}当G为非平凡图0当G为平凡图
( = 使G变成不连通或平凡图所需去掉的最少边数。）
易见，当G为非平凡连通图时， = G的最小键的边数。
==2=1,=2=1,=2==0=2,=3例。 = 0 G平凡或不连通。 = 1 G连通且含割边。 (Kn)= n-1 ( n > 0 )。 当G为简单图时，
= -1 G K 。 称 图G为 k-边连通的（k-edge connected） (G) k 至少去掉k条边才能使G变成不连通或平凡图。
例如，所有非平凡连通图都是 1-边连通的。
称 顶点子集V’为G的顶点割(vertex cut) G - V’ 不连通。
称 顶点子集V’为G的k-(顶)点割(vertex cut) V’为G的顶点割，且 V’ = k 。显然，当G为无环连通图时， v 为G的1-点割 v为G的 割点。 完全图无点割。 G的连通度(connectivity)
(G)min V' V'为G的点割当G有二不相邻接顶点时-1其它
（ = 使G变成不连通或平凡图所需去掉的最少的顶点数。）
例。当 3时， = 1 G连通且有1-点割。 (K) = -1 。
(G) = -1 G的基础简单图为完全图。 称 图G为k-连通的（k-connected） (G) k 至少去掉k个顶点才能使G变成不连通或平凡图。 例如，所有非平凡连通图都是 1-连通的。
定理3.1 。
==016
证明：先证 ：当G为平凡图时， 0 ，结论成立；当G为非平凡图时，选取v使d(v) = , 则 E’ =
v, v 是G的一个边割，因此
结论成立。 再来证 ： 不妨设G为简单、连通、非完全图，于是 -2。 任取一 -边割B，及B中任一边 e = xy 。 今，在B-e 的每边上各取一个端点使之不等于x及y 。令这些端点的集合为S。易见，
S -1 。 记 H = G-S 。
(i) 若H不连通，则S为G的点割，从而 S -1 。
(ii) 若H连通，则e = xy 为H的割边。但，(H) = (G)- S - ( -1) 3 ，因此，x与y必有一个为H的割点，设为 x 。于是
S {x} 为G的点割，故
S + 1 。
习题 3.1.1 (a) 证明：若G是k-边连通的，且k > 0 ，又E’为G的任k条边的集合，则 （G-E’) 2。
(b) 对 k >0，找出一个k-连通图G以及G的k个顶点的集合S，使(G-S)> 2 。 3.1.2 证明：若G是k-边连通的，则 k/2 。
3.1.3 (a) 证明：若G是简单图且 -2，则 = 。 (b) 找出一个简单图G，使得 =-3且 < 。
3.1.4 (a) 证明：若G是简单图且 /2，则 = 。
(b) 找出一个简单图G，使得 = [（/2）-1] 且 < 。
3.1.5 证明：若G是简单图且 ( +k-2)/2 ( k < )，则G是k连通的 。 3.1.6 证明：若G是正则简单图，则 = 。
3.1.7 证明：若l，m和n是适合0 块（block） 无割点连通图。 显然，当 v 3时， G为块 G为无环、2-连通图。 例。 v 3的块中无割边。 定理3.2 (Whiteney,1932) 当 v 3时， G为2-连通图 G中任二顶点间则至少被两条内部不相交（internally disjoint）的路连接。 （两条路P与Q内部不相交 P与Q无公共内部顶点） 证明： ：显然，G连通，且无1-点割，因此G为2-连通。 ：对G中二顶点间的距离d(,)进行归纳。 当d(u,v) = 1 时（即uv为G的边)， 因G为2-连通，边uv是G的非割边( ∵ 2)。因此，由定理2.3 ，边uv在G的某一 圈内，成立。 假设定理对 d(,) xP因此，由归纳假设，存在二内部不相交的 （u,w)-路P及Q。 uvQw 因G为2-连通，G-w 中一定存在一 (u,v)-路P’ 。令x为P’在 P Q 中的最后一个顶点。不 P’ 失一般性。不妨设x在P上。这时G中有二内部不 17 相交的(u,v)-路： ( P的(u,x)-节)( P’的(x,v)-节) Quv。 推论3.2.1 当 3时， 图G为2-连通的 G的任二顶点共圈。 证明：由定理3.2 ，显然。 称边e被剖分 用连接e的两端点的长2为的新路去替换e。 容易验证，当 3时，块的一些边被剖分后仍然保持是块。 推论3.2.2 G为块 G的任二边共圈。 证明： ：当 2时，显然成立。当 3时，将G的任二边e1 和e2 分别用新顶点v1 和v2 加以剖分，得新图G’ 。它是块，因此为2-连通的。由推论3.2.1知，v1 与v2 共圈。从而e1 与e2共圈。 ：由条件知，G无环。只要再证G也不会有割点即可：假设u为G的割点。由割点定义知，存在E(G)的一个2-划分（E1 ,E2 )使边导出子图G[E1]与G[E2]恰只有一公共顶点u。由边导出子图定义知，E1 和E2 各含一边 e1 和e2 ，它们有一公共端点u。从而，易见， e1 和e2不能共圈，矛盾。 附录 Menger 定理 若 k+1，则 G为k-连通的 G中任二不同顶点至少被k-条内部不相交的路所连接。 G为k-边连通的 G中任二不同顶点至少被k-条边不重的路所连接。 当一个图G有割点时，我们可沿G的割点将G逐步划分为一些不含割点的极大连通子图，它们每个称为G的块。例如 性质 划分图GG的块 (1) G的两个块之间至多有一公共顶点，它一定是G的割点。 (2) G的任一割点至少是G的两个块的公共顶点。 (3) G是它的块的边不重并。 (4) 含割点的连通图G中，至少有两个G的块每个恰含G的一个割点。 * (5)任一图G中，易证，两边之间的共圈关系是一等价关系。它将E(G)划分为一些等价类 (E1 ,E2 ,...,Ep )，而每个G[Ei ]就是G每个的块。 习题 3.2.1 证明：一图是边连通的当且仅当任二顶点至少被两条边不重的路所连接。 3.2.2 举例说明：若P为2-连通图G中一给定的(u,v)-路，则G不一定有一条与P内部不相交的（u,v)-路。 3.2.3 证明：若G没有偶圈及孤立点，则G的每个块为K2 或奇圈。 3.2.4 证明：不是块的连通图G中，至少有两个G的块每个恰含G的一个割点。 3.2.5 证明：G的块的数目 = (b(v)1) ，其中b(v)是G中含顶点v的块的个数。 vV3.2.6 设G为2-连通，而X和Y 是V的不相交子集，它们各至少包含二顶点。证明：G包含二不相交的路P和Q使得 (i) P和Q的起点在X中； (ii) P和Q的终点在Y中； (iii) P和Q的内部顶点都不在X Y中。 3.2.7 叙述求图的块的好算法。 18 可靠通信网的建设 及越大越可靠（造价越贵： ） 问题 已给赋权图G及正整数k，求G的最小权k-连通（k-边连通）生成子图。 解 当 k = 1 , optimal tree (connector prob.) 当k > 1 , NP-hard prob. 当每边权 1且G为任意图时，问题变成求边数最少的k-连通生成子图。( 仍然是 NP-hard prob.) 当G K 且每边权为 1 时，Harary (1962)作出边数最少的G的k-连通（k-边连通）生成子图Hk,（边数={k/2}) （∴有好算法。） Hamilton 圈与Euler 环游 Euler 环游 环游（tour） 通过图中每边至少一次的闭途径。 Euler环游 通过图中每边恰一次的闭途径。 Euler迹 通过图中每边的迹 。 通过图中每边恰一次的途径。 （可“一笔画成”。） Euler图 包含Euler环游的图 包含Euler闭迹的图。 本身为闭迹的图。 定理4.1 设G为非空连通图，则 G为 Euler图 G中无度为奇数的顶点。 证明： ：令 C = u0 e1 u1 e2 u2 ...e u (u = u0 )为G的一 Euler环游 ，起点为u0 。则对任一顶点v u0 ，当v每次作为内部顶点出现于C时，C上有二边与v相关联。由于C上包含了G的所有边且不重复，因此d(v)=偶数。类似地，d(u0)=偶数。 ：反证，假设存在非空连通图，它的每个顶点的度都是偶数，但却不是Euler图 。在这种图中选取G使其边数最少。 由于 (G) 2，G包含圈。令C为G中的最长闭迹。由假设，C不会是 Euler环游。因此 G - E(C) 中一定有一分支G’ 使(G’)>0。由于C本身为 Euler图，（由定理的必要条件知）C中每个顶点的度都是偶数，因此G’中无度为奇数的顶点。但 (G’) < (G) 由G的选择知，G’中含一 Euler环游 C’。 又，由于G连通，C与C’至少有一公共顶点，设为v，且不妨设它同时为它们的起点。于是， CC’ 是G的一闭迹，其长大于C的长，矛盾。 附录 定理4.1 :之新证法（J.G.T.Fall 1986)： 对 进行归纳。当 =2时，显然成立。只要再考虑 3情形。 假设对 < q成立，而 (G)=q 。 选取顶点v ，使v有二不同顶点u及w与它相邻 。考虑图 19 H = (G - {uv,vw})+uw （uw 为一新加边——不管G中是否有以u，w为两端点的边） 显然， (H) 2 , u (H) = q-1 , v dH(x) = 偶数 x V 。 w(i) 当(H)=1时，由归纳假设，H中有Euler环游 C’。把C’ 中 u一边uw代之以路uvw，即得G的Euler环游 。 C'(ii) 当(H)=2时，由归纳假设，H的二分支各有其Euler环游 C1v 及C2 。不妨设uw在C2 中。将C2中的边uw代之以迹 uvC1vw，即得G w的Euler环游 。 C1C2 推论4.1 若G连通，则 G有一Euler迹 G中至多有二度为奇数顶点。 证明： ： 类似定理4.1中 ：的证明。 ： 若G中无度为奇数顶点，则由定理4.1 ，G中有Euler迹。否则，G中恰有二度为奇数顶点，设为u，v 。 考虑图 G + e ， 其中e为连接u与v的新边。显然，G+e中 无度为奇数顶点，从而包含一Euler环游 C = v0 e1 v1 e2 v2 ...ev ， 其中，v = v0 =u ，v1 =v 。易见 v1 e2 v2 ...ev 就是G的Euler迹。 习题 4.1.1 若可能，画出一个 为偶数，而 为奇数的Euler图。否则说明理由。 4.1.2 证明：若G无奇点，则G的每个块也是Euler图 。 4.1.3 若G无奇点，则存在边不重的圈C1 ,C2 ,...,Cm 使得 E(G) = E(C1) E(C2) ... E(Cm)。 4.1.4 若连通图G有2k >0 个奇点，则G中存在k条边不重的迹Q1 ,Q2 ,...,Qk 使得 E(G) = E(Q1) E(Q2) ... E(Qk)。 4.1.5 设G为非平凡Euler图 ，且v V。证明：G中任一条 以v为起点的迹 都能延伸成一Euler环游 当且仅当 G-v为林。 （O.Ore） 中国邮递员问题 问题 在一赋权图G中，求一最小权环游 （即最优环游）。 当G 为Euler图时，其任一Euler环游 都是最优环游，此时有求最优环游的好算法，如 Fleury算法 （“过河拆桥，尽量不走独木桥“） 任取一顶点v0 ，令w0 = v0 。 若迹Wi =v0 e1 v1 ...ei v i已取定，选 ei+1 E\\{e1 ,..., ei}使 (i) ei+1 与 v i相关联； (ii) 除非无奈，选ei+1 使它不是 Gi = G-{e1 ,..., ei} 的割边。 3. 若 2. 不能再进行下去，停止。 定理4.7 若G为Euler图 ，则由Fleury算法求得的G中的迹，是G的一Euler环游 。 证明：令 Wn =v0 e1 v1 ...en vn Fleury算法求得的G中的迹， 显然 dGn (vn ) = 0 , vn = v0 。 20 假设Wn 不是Euler环游 ，令 S = { v dGn (v ) > 0 } ， S = V\\S 。 易见， S ； vn S 。 令 vm 为Wn 在S中的最后一个顶点，则，显然， S,SGmem1 。 又， dGn(v) = 偶数， v V 。 因此Gn 中无割边，特别地，Gn中与vm相关联的任一边e是Gn中的非割边，因而也是Gm中的非割边。但 em1 e (∵em1 Gn )，于是在Gm 中，割边em1 与非割边e都和vm 相关联，而迹Wn却取的是割边em1，这与算法之 2.(ii) 相矛盾。 定理之另证： 其实只要再证以下断言即可： 断言 在算法进行过程中，每个Gi 都是G的生成子图，其中只有一个分支是非空的（即其余分支每个都是孤立顶点），且v i与v0 同在该非空分支中。 证明：对i进行归纳。当i=1时，G1 = G- e1 ，由于G中无割边，G1 连通，从而结论成立。假设当i≤n-1时都成立，来证当i = n （＜ε）时也成立： 由归纳假设，Gn-1 = G - {e1 ,......,en-1 }中，vn-1 和v0 在其唯一的非空分支中。于是，算法2.(i) 所选 vn-1 的关联边en 必在该分支中。 当en不是Gn-1的割边时，（对Gn ）结论成立。 当en是Gn-1的割边时，由算法知，Gn-1中与vn-1相关联的边必都是Gn-1的割边。 由习题（见下）知，与vn-1相关联的边中至多有一条割边，从而Gn-1中与vn-1相关联的边恰只有en这条边。因此，Gn中原Gn-1的非空分支变成一个孤立顶点vn-1及一个含vn与v0 的非空分支 。结论仍成立。 习题 若连通图G中只有二奇点，则与任一奇点相关联的边中至多有一 条是G的割边。 中国邮递员问题 在一赋权图G中，求一最小权环游 （即最优环游） (i) 找赋权连通图G的一个Euler母图G*，它是由重复 （duplicated）G的一些边而得，且使 w( E(G*) \\ E(G) ) = min ； (ii) 在G*中找出其Euler环游 。 [ 附录（关梅谷，1960）(书： “Selected Topics in Graph Theorey 2 ” , p.35) 连通图G（每边权 1）中的“邮路”（最优环游）为C 在C中G的每边至多出现两次，且G的任一闭迹中至多有半数的边重复 出现于C。] 当赋权图G中恰只有二度为奇数顶点u, v时,G*可由G加上(重复)G中的最短(u, v)-路P而得。 证明：易见，G1* = G*[E* \\ E ] 中只有u， v 为奇点，它们一定在G*的同一分支中。令P*为其中的（u，v）-路，则有 w( E* \\ E ) w(P*) w(P) 。 但 G+P 也是G的一Euler母图，故 G* = G + P 。 当G中有 4 个奇点时，已由J.Edmonds and E.L.Johnson 解决（1972）。 Hamilton 圈 Hamilton路 生成路（spanning path ） Hamilton 圈 生成圈 Hamilton 图 包含Hamilton 圈的图 定理4.2 G为Hamilton 图 (G-S) S S V 非Hamilton 图 21 证明：令C为G的一个Hamilton 圈 ,则对任一 S V 必有 (C-S) S ， 但 (G-S) (C-S) 。 注意，定理4.2之逆不成立。 例如，Pertersen图 满足定理条件，但它是非Hamilton 图 。 约定 本节只讨论简单图。 定理4.3 （Dirac，1952） 3的简单图G中，若 /2， Petersen图则G为Hamilton 图 。 证明：反证，设G为 3满足 /2的极大非Hamilton 简单图。（即任取一反例，在保持其为非Hamilton、 简单图的前提下，尽量加边，直到不能再加为止。取之为G。）因 3，G不能是完全图。任取G中二不相邻接顶点u及v，则 G+uv 为Hamilton 图，且其中的每个Hamilton 圈均含边uv。从而G中有Hamilton 路 v1 v2............v 其中v1 = u, v = v 。 令 S = { vi u vi+1 E } T = { v j v jv E } 易见， v ST ， ST < 。 又， ST = 。 (不然，假设存在vk ST ，则G中有Hamilton 圈 v1 v2 。。。vk v v。。。vk+1 v1 ， 矛盾） ∴ d(u) + d(v) = S + T = ST < 这与 /2 相矛盾。 推论4.4.1 ( Bondy & Chvatal , 1974) 设u, v 为简单图G中二不相邻顶点，且 d(u) + d(v) ，则 G为Hamilton 图 G+uv 为Hamilton 图 。 证明： ：显然 。 ： 反证，假设G为非Hamilton 图 ，则由定理4..4之证明知, d(u) + d(v) < 矛盾 。 闭包（closure）c(G) G的生成母图。 它是由G开始，通过反复将其中不相邻接而度之和 的 顶点对 用新边连起来，直到不能再进行为止所得的图。 引理4.4.2 c(G)是唯一确定的（well define）。 证明：假设G’及G’’为G的二闭包 ，而 e1 ,.........,em 及 f1 ,...........,fn 为构成它们时加上去的新边（按先后顺序）序列。先证 ：先证每个ei E(G’)。假设不然,令ek+1 =uv为e1 ,.........,em 中第一个 E(G’’)的新边。记 H = G+{e1 ,.........,eK } 。 由G’之定义知 dH(u) + dH(v) 。 但H G’’ ， ∴ dG’’(u) + dG’’(v) dH(u) + dH(v) 。 而 uv E(G’’), 这与G’’之定义矛盾。 同理，每个fj E(G’) 。故 G’ = G’’ 。 22 定理4.4 简单图G为Hamilton 图 c(G)为Hamilton 图 。 推论4.4 设G为 3的简单图，则 c(G)为完全图 G为Hamilton 图 。 例* 设简单连通图G中 2 ，则G含一长 2 的路。 例 将二部图G = (X,Y,E) ， X = Y ，中X的每对顶点都连起来得图H。 则 H有Hamilton 圈 G有Hamilton 圈 。 例 若简单2-连通二部图G = (X, Y, E)中, X = Y - 1 = n ,且 d(x) n , x X , 则Y的任二顶点间都有Hamilton 路相连。 Hamilton 图 习题 4.3.1. 证明：若 (a) G不是2连通图；或者 (b) G是二划分为（X，Y）的二部图 ，且 X ≠ Y ； 则G为非Hamilton 图 。 4.3.2. 一只老鼠边吃边走通过一块3立方体的奶酪，想走遍每个子立方体（共27个）。若从某个角落开始，它能否最后到达立方体的中心？ 4.3.3. 证明：若G有Hamilton 路，则对于V的每个真子集S，有(G-S) S + 1。 4.3.4. 若 3的简单图G中，C21 ，则G为Hamilton 图 。 4.3.5. 座位的教室中，不可能让每个学生都作一上下左右移动，使每个人都换了座位。 4.3.6. 若二部图G=（X，Y；E）中，|X| = |Y| = n，且 >n/2 ，则G为Hamilton 图 。 4.3.7. 5个人围桌而坐，总有一 新就座法，使每人的邻座都不相同。 4.3.8. 对下列问题给出一好算法： (a) 构造一个图的闭包。 (b) 若某图的闭包为完全图，求该图的Hamilton 圈 。 4.3.9. 对任正整数n，完全3-部Kn,2n,3n为Hamilton 图 ；而完全3-部Kn,2n,3n+1为非Hamilton 图 1 旅行售货员问题(travelling salesman prob.) 问题 在赋权完全图中找最小权Hamilton 圈（最优圈） 。 （NP-hard prob。） （问题 任给一图G， G是否为Hamilton 图 ？ （NP-complete prob。）） 代替办法 找一reasonably good solution。例如，先找一Hamilton 圈 C=v1v2 ...v v1 ，再加以改进： 对任i与j, 1 w(vi vj ) + w(vi+1vj+1) < w(vivi+1) + w(vjvj+1) 则 Cij是C的一个改进。 反复进行上述步骤，直到不能再改进为止。所得Hamilton 圈 一般不会是最优圈，但可能是比较好的。上述步骤也可从不同的Hamilton 圈作为开始，反复进行之。令W’为所 * 求得最小权，它可作为最优圈C的权的上界。 * w(C) W’ * 下界的估计式 设v为最优圈C上任取的一个顶点，则 * C - v 为G - v中的一生成树。令T为G - v 中的最优树，则 * w(T)+w(e)+w(f) w(C) ， 其中e，f为G 中与v相关联的边中权之和为最小的二边。 习题 * 4.4.1 设赋权完全图G的权满足三角不等式，即对任x,y,z V 都有 w(xy) + w(yz) w(xz) 。 证明：G中最优圈的权最多是2w(T), 其中T是G中的一最优树。 23 匹配 匹配 匹配（matching） M E M中的边都是link，且互不相邻接。 当uv M时，称u与v在M下相匹配；称M饱和（saturated) u与v。称u与v为M-饱和的。类似地，可给出一顶点x为M-不饱和的的定义。 M为图G的完美匹配 G中每个顶点都是M-饱和的。 M为图G的最大匹配（maximum matching ） 。。。 P为G中的M-交错路(M-alternating path) P的边交替地属于M及E\\M。 P为G中的M-可扩路（M-augmenting path ) P为M-交错路，且起点与终点都是M-不饱和的。 定理5.1 (Berge,1957) M为G中的最大匹配 G中不存在M-可扩路。 证明： ：假设G中有M-可扩路P，则 M’ = ME(P) 也是G的匹配， 且 M’ = M +1，这与M 为最大匹配相矛盾。 ：反证，假设M不是最大匹配，取G中任一最大匹配M*。。令 H = G[ MM*] 。 显然， dH(v) = 1 or 2 v V(H) 。 因此，H的每个分支都是一圈或路，由M及M*的边交错组成。但 M* > M ，H中一定有一分 支是一条路P，且其起点与终点都是M*饱和的。从而P是G中的M-可扩路， 矛盾。 习题 5.1.1 (a) 证明：每个k-方体都有完美匹配(k 3)。 (b) 求K2n与Kn,n中不同的完美匹配的个数。 5.1.2 证明：一树中最多只有一个完美匹配。 5.1.3 对每个k>1，找出一个无完美匹配的k-正则简单图的例子。 5.1.4 两人在图G上做游戏，交替地选取不同的顶点 v0 ,v1 ,v2 ,.........，使对每个i > 0 ，都有vi 与 vi-1 相邻。最后一个顶点的选择者胜。证明：第一个选点人有一得胜策略当且仅当G没有完美匹配。 5.1.5 G的k-正则生成子图称为G的k-因子。若G存在边不重的k-因子H1，H2， ……，Hn，使得 G = H1H2…… Hn ，则称G为k-可因子分解的 。 (a) 证明：① Kn,n与 K2n是1-可因子分解的； ② Peterson图不是1-可因子分解的。 (b) 下面的图中哪些有2-因子： (c) 用Dirac定理若G是简单图， 是偶数，且 1+/2 ，则G有3-因子。 5.1.6* 证明：K2n+1可表为n个连通的2-因子的并。 5.1.7 证明：任连通偶图G = （X,Y, E）的2-划分（X，Y）是唯一的。 24 偶图的匹配和覆盖 邻集（neighbour set） N(S) （S V）：G中所有与S中顶点相邻接的顶点集合。 定理5.2 （Hall’s theorem,1935) 在偶图G=(X,Y,E)中 G包含使X中每个顶点都饱和的匹配 N（S） S S X （*） 证明： ：显然。 ： 反证，假设存在偶图G，它满足条件（*）但不包含使X中每个顶点都饱和的匹配。* * 令M为G的最大匹配，u为X中M不饱和的顶点。记 * Z = { v M-交错（u，v）-路 } ** 由于M 为最大匹配，由定理5.1 ，u为Z中唯一M-不饱和顶点。令 S = ZX ， T = ZY 。 ** 显然， S\\U 与T 的顶点在M 下相匹配（注意到：任一M-边若有一端点在Z中，则其另一端一定也在Z中）。因此， T = S - 1 ； N(S) T 。 但 N(S) T ， 故 N(S) = T ，从而 N(S) = T =S- 1 <S 。 矛盾。 推论 5.2 (marriage theorem) 若G 为 k-正则偶图（k>0 )，则G有完美匹配。 证明：设G的2-划分为(X, Y)，则 kX=E=kY ， X = Y 。 又，对任S X，令E1和E2 分别为与S和N(S)相关联的边集。易见， E1 E2 。 ∴ kS = E1 E2 = kN(S) ∴ S N(S) S X 。 故G中有使X中每个顶点都饱和的匹配M，它也是完美匹配。 称 K（ V）为G的一个覆盖（covering） G中每边至少有一端在K中。 最小覆盖（minimum covering）K 。 对G中任一覆盖K及任一匹配M ，显然，恒有 M K。 特别地，有 M K 。 引理5.3 设M与K分别为G中的匹配与覆盖，如果 M = K 则M为最大匹配，K为最小覆盖。 （证明：略） * * ~~M=K 。 证明：设G的2-划分为（X，Y）。记 * U = { u X u为M-不饱和的 } * Z = { v V M-交错（u，v）-路 } S = ZX， T = ZY 。 ** 与定理5.2之证明类似，我们有： T中每顶点都是M-饱和的；T与S\\U中顶点在M下相匹配；N(S) = T。 记 25 ~定理5.3 (Konig’s theorem,1931) 设 M，K分别为偶图G的最大匹配和最小覆盖，则 * ~ ~K= (X\\S) T 。 ~~易见，G中每边至少有一端在K 中，即K 为G 的覆盖（不然，与N(S) = T相矛盾）。又，显然， ~* M=K 。 再由引理5.3知为最小覆盖。 习题 5.2.1 证明：一个55方格棋盘去掉其对角上的两个11方格之后，不可能用12长方格恰好添满。 5.2.2 (a) 证明：偶图G有完美匹配当且仅当对 所有S V 都有 N(S) S 。 (b) 举例说明：去掉偶图这个条件之后，上述不成立。 5.2.3 对于k > 0，证明： (a) 每个k-正则偶图都是1-可因子分解的； * (b) 每个2k-正则图都是2-可因子分解的 。 5.2.4 设A1 ，A2 ，……，An 是某集S的子集。 族（A1 ，A2 ，……，An）的一个相异代表系是指S的一个子集{ a1 ，a2 ，……，an }使 ai Ai （1 i n），且 ai aj （当ij）。证明：（A1 ，A2 ，……，An）有一个相异代表系 当且仅当 AiJi J J {1,2,...,n} 。 5.2.5 矩阵的一行或一列统称一条线。证明：一（0,1)-矩阵中 ，含所有1元素的线的最小条数 = 两两都不在相同线上的1元素的最大个数。 5.2.6 (a) 证明：Hall定理的一个推广：偶图G =（X,Y; E) 的最大匹配的边数是 X - max{ S-N(S) } 。 SX (b) 试证：若G 为简单偶图，且X=Y=n 及 > (k-1)n ，则G有边数为k的匹配。 * 5.2.7 由Konig定理推导Hall定理。 * 5.2.8 若非负实数矩阵Q的每行元素之和均为1，每列元素之和也均为1，则称Q为双随机矩阵。称一矩阵为置换矩阵如果它是每行和每列均恰只有一个1元素的 （0，1）矩阵（∴是双随机的）。证明： (a) 每个双随机矩阵一定是个方阵； (b) 每个双随机矩阵Q都可表为置换矩阵的凸线性组合，即 Q = c1 P1 +c2 P2 +……+ck Pk 。 其中每个Pi都是置换矩阵，每个ci都是非负实数，且 ci1ki1 。 5.2.9 若偶图G=(X,Y,E)中，X中每顶点的度Y中每顶点的度，则G有使X每顶点都饱和的匹配。 * 5.2.10 设偶图G=(X,Y,E)中，Y’为匹配M在Y中的端点集，则存在G的最大匹配M，其端点集包含Y’。 完美匹配 称H为G的奇分支（odd component） H为G的分支，且其顶点数为奇数。 称H为G的偶分支（even component） ……。 记 o(G) = G中奇分支数。 定理5.4 ( Tutte,1947) G有完美匹配 o(G-S) S S V (*) 证明：（Lavasz证法）只要对简单图情形加以证明即可。 ： 设G有完美匹配M。对任S V，令 G1 ，……，Gn 为G-S中的奇分支。因每个Gi的顶点数都是奇数，每个Gi中至少 有一顶点u i 与S中一顶点vi 在M 下相匹配。从而 o(G-S) = n = {v1 ，……，vn} S 。 26 ： 反证。假设存在图G 满足条件（*），但不含完美匹配。令G 为G的不含完美匹配的极大生 * 成母图。由于G-S是G-S的生成子图， * o(G-S) o(G-S) S S V 。 *** 即G满足条件（*），又，上式中令S=得o(G)=0，因此 (G)=偶数。 令 * U{vV(G*)dG*(v)1。 因G不含完美匹配，U V。 * 断言 G-S是一些完全图的不相交并。 ** 从而，由于 o(G-U) U ， G-U中至多有U个奇分支。于是，由断言易见， ** G 中有完美匹配，这与G 之假设矛盾。 * 来证断言 反证。假设G-U有一分支不是完全图，则其中一定存在3个顶点x，y，z使 ** xy, yz E(G) ， 而 xzE(G) ** 又，因 y U，一定存在 w V(G-U) 使 yw E(G)。 令 ** M1 与 M2 分别为 G+xz 与 G+yw中的完美匹配。 * 考虑 G+{xz，yw} 中 M1M2 的边导出子图 H 。显然，H中顶点的度都是2，因而H是一些圈的不相交并。且每圈都是偶圈，由M1 与M2 的边交错组成。 情况1 xz与yw不在H的同一圈中： * 设yw在圈C上，则C中所有M1 边及C外所有M2 边一起构成G 的一个完美匹配，矛盾。 情况2 xz与yw同在H的某一圈C上： 不妨设x，y，w，z以这顺序出现于C上。这时，C的yw……z节中的所有M1 边，及不在 * 该节中的所有M2 边，以及边yz ，一起构成G 的一个完美匹配，矛盾。 推论5.4 (Peterson,11) 每一不含割边的3-正则图都有一完美匹配。 证明：对任S V，令 G1 ，……，Gn 为G-S中的所有奇分支。记mi 为一端在Gi中而另一端在S中的边数。则 mivV(Gi)d(v)2(G)3(G)2(G)奇数。 iii但G中无割边，因此mi 3。从而 3S= d(v)mvSi1ni3n 。 ∴ S n = o(G-S) S V。 故由定理5.4，G有完美匹配。 习题 * 5.3.1 用Tutte定理推导Hall定理。 5.3.2 推广推论5.4：若G是（k-1）边连通的k-正则图，且 是偶数，则G有完美匹配。 5.3.3 设G为一树，证明： G有完美匹配 o(G-v) = 1 v V 。 * 5.3.4 证明Tutte定理的推广： G的最大匹配的边数 = ( -d)/2 ，其中 dmax{o(GS)S} （C.Berge) SV 人员分派问题 问题 n个工人x1 ，……，xn 及n个工作y1 ，……，yn ，已知每个工人都胜任一些工作。能否使每个工人都分派到一件他所胜任的工作？（ （the personnel）assignment prob.) 解 在偶图G=(X,Y,E),X=Y, 中求出其完美匹配（若存在的话）。 Hungarian method (Edmonds,1965) 以任一匹配M作为开始。（可取M=） ① 若M饱和X的每个顶点，停止（M为完美匹配）。否则，取X中M-不饱和顶点u， 27 S{u}，T 。 ② 若N(S)T,转到③；否则，N(S)=T,停止（无完美匹配）。 ③ 取 y N(S)\\T 。若y为M-饱和的，设 yz M ，则 SS{z} ， TT{y} ， 回到②；否则，存在M-可扩路P。 MME(P) ， 并回到① 。 注1 算法用生长“以u为根的M-交错树”的方法 ，来系统地搜索M-可扩路。树中除u外都是M-饱和的，直到碰到第一个 M-不饱和的顶点时，即得一M-可扩路。当树不能再生长下去时，即为N(S)=T之时。 注2 本算法是个‘好’算法： 从一个M到下一个，至多进行X次搜索运算；M至多扩大X次 。 习题 5.4.1 试述如何利用Hungarian算法求偶图的最大匹配。 Optimal assignment problem 问题 求赋权图G = Kn，n 的最大权匹配。 称l为（feasible vertex labelling)（f.v.l.) l为V上的实函数，且满足： l(x)+l(y) w(xy) x X， y Y 。 w(xy)}l(x)max{yY例。 下面是一可行顶点标号： l(y)0记 xXyY ElxyEl(x)l(y)w(xy) Gl (相等子图，equality subgraph） 以El为边集的G的生成子图。 **定理5.5 设偶图G的可行顶点标号l使Gl 包含一完美匹配M，则M是G的最优匹配。 证明：显然，M也是G的完美匹配，且 *w(M*) *eM*w(e)l(v) 。 vVeM但对G的任一完美匹配M有 w(M)w(e)l(v) 。 vV因此w(M) w(M)，即M是G的最优匹配。 下面是求最优匹配算法的基本思想 ： 任取一f.v.l. l作为开始。定Gl ，并在Gl 上任取一匹配M作为开始的匹配。用Hungarian算法在Gl 上找完美匹配。若找到，它就是G的最优匹配；否则Hungarian算法停止于某匹配M’（不是完美匹配）及一M’交错树H，它不能再“生长”。将l适当修改成新的f.v.l. l：使G~仍包含M’及H，且H在G~中又可继续“生长”。重复上述过程。 ll Kuhn-Munker algorithm （1955，1957；Edmonds改写（1967）） 以任f.v.l. l作为开始。定Gl ，并在Gl 上任取一匹配M作为开始的匹配。 ① 若M饱和X的每个顶点，则M为最优匹配，停止；否则，任取一M-不饱和顶点u， S{u}， T 。 ② 若NGl(S) T，转到③；否则，NGl(S)=T。计算 *~ 28 l = min{l(x)l(y)w(xy)} xS~yT及f.v.l. l ： vSl(v)l~ ll(v)lvT l(v)其它~ l l ， Gl G~ 。 l ③ 选取 yNGl(S)\\T，若y为M-饱和的，则存在 yxM ， 作 SS{x}， TT{y}， 并转到② ；否则，令P为Gl中的M-可扩-(u,y)路， MME(P) ， 并转到① 。 2 注1 算法中每计算一次新的Gl的计算量为O()；在找到M-可扩路之前，至多进行 X次 搜索（每次可能作一次新的Gl的计算）；而初始匹配M至多扩大X次。因此是个‘好’算法（计算复 4 杂性为O() ) 注2 本算法也可用于解人员分派问题。 习题 5.5.1 所谓n×n矩阵的一条对角线是指它的任n个两两不同行、不同列元素的集合。对角线的权是指它的n个元素的和。试找出下列矩阵的最小权对角线： 4786456565851213710791091146 （答：权=30） 78 边着色 边色数 前提 本章只讨论无环图。 k-边着色（k-edge colouring）C k种色在图G的边集上的一种分配。 C是E(G)的一个k-划分，即 C =（E1 ，。。。，Ek） （注：允许Ei= ） 边着色C是正常的 每个Ei都是G的一个匹配。 G为k-边可着色的（k-edge colurable） G有一正常k-边着色。 存在E(G)的一个k-划分 C =（E1 ，，使每个Ei 都 。。。，Ek） 是G的一个匹配。 （注：允许Ei= ） （显然，G为k-边可着色的 G为l-边可着色的 （l k） ） G的边色数（edge chromatic number） (G) = min{ k G为k-边可着色的} G为k-边色的（k-edge chromatic） (G) = k。 例。 n个人举行一些两谈，每次会谈用一个单元时间。问最少要多少单元时间，才能安排完 29 所有会谈？ 例。Peterson图有 = 4。 显然， 。 称色i表现（rrepresented）于顶点v 与v相关联的某一边有色i。 引理6.1.1 设连通图G不是奇圈，则G有一2-边着色，使该二色表现于G的每个 度 2的顶点。 证明：不妨设G为非平凡的。 (A) 若G为Euler图： ① 若G 为一圈： 则G为偶圈，从而G的一个正常2-边着色满足要求。 ② 若G不是个圈：则一定存在顶点v0 ，使d(v0) 4 (∵Euler图每个顶点的度均为偶数）。 令 v0 e1 v1 e2 。= v0 ）。令 E1 与 E2 分别为Euler环游中下标为奇数与偶。。e v 为G一的Euler环游 （ v 数的边子集。则G 的2-边着色 C=（E1，E2）满足要求。 (B) 若G为非Euler环游 ：往G中加一新顶点v0 ，并将v0 与G中每个度为奇数顶点都用一新边连起来，得图G’ 。显然，G’为一Euler图 。令v0 e1 v1 e2 。v （ v = v0 ）为G的一Euler。。e 环游 。与(A)②一样定义 C =（E1，E2），易见 C’ = ( E1 E，E2 E） 满足要求。 记号 c(v) = 边着色C表现于v的不同颜色数。 显然， c(v) d(v) v V 。 C为正常边着色 c(v) = d(v) v V 。 称G的k-边着色C’ 为其k-边着色C的一个改进 c'(v)c(v) 。 vVvVC为最优k-边着色（optimal k-edge colouring） C不能再改进 。 引理6.1.2 设 C =（E1 ，。。。，Ek）为G的一个最优k-边着色。若G中有一顶点u及色i与j，使i不表现于u，而j在u上至少表现2次。则G[Ei Ej ]中含u的分支是一奇圈。 证明：令H为G[Ei Ej ]中含u的分支。假设H不是奇圈，由引理6.1.1.，H有一2-边着色，使该二色表现于H的每个度2顶点上。以这方式，用色i与j对H重新边着色，得G的一个新的k-边着色C’。显然， c’(u) = c(u) + 1 c(v) c(v) vu c'(v)c(v) 这与C为最优矛盾。 vVvV 定理6.1 设G为偶图，则 = 。 证明：反证，假设 > 。令C为G的一个最优-边着色，而u V为使 c(u) < d(u) 的顶点。于是u满足引理6.1.2.条件，从而G包含奇圈。这与定理1.2 相矛盾。 另一证法（Wilson）对 进行归纳。当 = 1 时显然成立。假设对 < 1 都成立，而 (G)= k 。任取G的一边 e = uv ，考虑 G’ = G - e 。 由归纳假设，G’ 有一 (G’)-正常边着色 C’={E1’,...,E(G’)}。 若 (G’) < (G)，则G显然有(G)-正常边着色，证完； 否则，(G’) = (G)。令Au与Av各 30 表示C’中不表现于u与v的色集。由于在G’中u与v都不是其最大度顶点，从而有 Au ，Av 。 ① 当 Au Av 时：将Au Av 之一色着在边e上，即得G的(G)-正常边着色。 ② Au Av = 时：任取色i Au 及色j Av 。令H为G[Ei’ Ej’] 中含u的分 支。易见，H是一条路，由色i与色j边交替组成。因此，v一定不在H上（不然，H的第一条边有色j，最后一边有i ，从而其长为偶数。这导致G中含一奇圈H + e，矛盾。）对换H上的色i与j，得G’的另一正常 (G’)-边着色，其中在u与v上色j都不表现。 再将色j着在e上，即得G的正常 (G)-边着色 。 习题 6.1.1 找出一适当的边着色以证明(Km,n) = (Km,n)。 6.1.2 (a) 证明：任一偶图G都有一-正则偶母图。 （不一定为生成母图！） (b) 利用(a)给出定理6.1 的另一证明。 6.1.3 叙述求偶图G的正常-边着色的好算法。 * 6.1.4 证明：若偶图G有 > 0 ，则G有一-边着色，使所有 种色在每一顶点上都表现。 Vizing定理 定理6.2 (Vizing,19) 对简单图G有 = 或 + 1 。 证明：（Bollobas）不妨设G中 除uv1外 都已用色 1,2,……, +1 进行了正常边着色。注意到，G的每个顶点上都至少有一色未表现。令u，v1 各有色i0，i1 未表现。我们可逐步找到不同的色、边序列： i0 ， i1 ， i2 ，……，ij ，…… ； uv1 ，uv2 ，……，uvj ，…… 。 其中， 色ij 是顶点 vj 上未表现的（任意取定的）一色； 边uvj 有色ij-1 。 j=2，3，…… 。 显然，上述过程至多进行到某l（ ）次而停止（无法继续满足上述条件）。 这时只有两种可能： (A) 色il 未表现于顶点u上（即没有一条u的关联vk+1(ik+1)边uvk有色il ）：重新进行边着色如下 vk(ik) ik-1ik uvj 改着色ij 1 j l-1 并抹去边uvl 上的色 il-1 。 i2u(i0)得G中除uvl 外的正常（ +1）边着色。其中u与vl v3(i3)i1上色il 同时不表现。将uvl 改着色il 即得G的正常（ +1） il-1no边着色。 vl(il)v2(i2)(B) il = ik 某 1 k l-1 ： 重新进行边着色如下 将uvj 改着色ij 1 v1(i1)j k v(i)表示v上色i未表现 并抹去边uvk+1 上的色 ik 。 易见， H = G[EE] 的每个分支是路或圈，由 i0ik色i0与ik的边交错组成，且 u，vk+1，vl 在H中的度 1。 从而，该三顶点不可能同时在H的一分支中。这时只有二可能情形： 31 ① u 与vk+1不在H的同一分支中：将H的含vk+1分支中 vk+1(ik+1)的色i0 与ik对换，得G 的除uvk+1外的正常（ +1）-边着色， vk(ik)其中u与vk+1上色i0都未表现。从而，G有一正常（ +1）-边 no着色。 ik② u与vl不在H的同一分支中： 再继续调整边着色如 i3u(i0)下， v3(i3)i 将uvj 改着色ij 并抹去边uvl 上的色 （il-1 ） 2il-1 k+1 j l-1 。 i1vl(il)v2(i2)易见，上述更动并未涉及色i0与ik ，因此H 保持不变。 将H中含u分支的色i0 与ik对换，得G 的除uvl外的正常（ v1(i1)+1）-边着色，其中u与vl上色i0都未表现。从而，G有一正常 （ +1）-边着色。 注1 对一般图有 Vizing定理 设G为无环图，则 + ，其中是G的重数（连接G中每一顶点对上的最大边数） 。 注2 NP-complete prob。已给简单图G，是否有 = ？ 注3 “2-边连通、3-正则、简单、平面图都有 = 3” “4-色猜想成立”。 习题 6.2.1* 找出适当的边着色以证明(K2N-1) = (K2N) = 2n-1 。 6.2.2 为奇数的非空正则简单图G有 = + 1 。 6.2.3(a) 设简单图G中 = 2n+1且 >n ，则 = +1 ； (b) 利用(a)证明： ① 若G是从有偶数个顶点的简单图中剖分一条边所得的图，则 = +1 ； ② 若G是从有奇数个顶点的简单k正则图中删去少于k/2条边所得的图，则 = + 1 。 6.2.4(a) 证明： 任一无环图G都有-正则无环母图。 (b) 利用(a)及习题5.2.3(b)证明：若G 是无环图且 是偶数，则 3 /2。 6.2.5 称G为唯一k-边可着色的，如果G的任意两个k-边着色都导致E有相同的划分。证明：每个唯一3-边可着色的3-正则图都是Hamilton 图 。 6.2.6 简单图的积图是指顶点集为V(G)×V(H)的简单图G×H，其中 (u,v)与(u’,v’)相邻 u = u’且v’ E(H)； 或v = v’且uu’ E(G) (a) 利用Vizing定理证明：(G×K2）= (G×K2) 。 (b) 试证：若H是非平凡的，且(H) = (H)，则(G×H) = (G×H)。 6.2.7 叙述求简单图G的正常(+1)-边着色的好算法。 * 6.2.8 证明： ≥2的简单图G有一(-1)-边着色，使得所有-1 种色在每个顶点上都表现。 排课表问题 问题 m位教师X1，……，Xm和n个班级Y1 ，……，Yn ，其中教师Xi要给班级Yj上pij节课。欲在最少节次p内排完所有的课。 将偶图G = (X,Y,E) (X=m ，Y=n)的边集E划分成互不相交的p个匹配(E1，……，Ep) 求偶图G的（= =p）-边着色。 由习题6.1.4知，上述问题有好算法。 当上述问题中若教室数有限时（ 教室数≥maxEi ），若要在p（ ）节内排完全部l（= E） 1ip节课，所需教室数c 。 32 lp 问题 能否适当排课，使全部l节课在p（ ）节内排完，且每节课所用 教室数 ？（∴Ei 1 i p ） ppp 引理6.3 设M，N为G的二不相交匹配，且M>N，则存在G的二不相交匹配M’，N’使M’ =M-1 ，N’ = N+1 ，且M’N’ = MN 。 证明：令H = G[MN]，则H的每个分支为一路或圈，由M及N的边交错组成。且由于M>N ，存在H的一个分支，它是路P， 起、止于M 边。因此 M’ = M E(P) 及 N’ = N E(P) 即为所求。 定理6.3 设G为偶图，p ，则存在G的p个互不相交的匹配使 E = M1 …… Mp 。 且 Mi 1 i p 。 证明：由定理6.1, E可划分为 个互不相交的匹配 M1，……，M 。 因此，对p ，G有p个互不相交的匹配 M1，……，M，……，Mp。 （令Mi= 当i > p) 使E = M1 …… Mp 。对边数差 > 1的两个匹配，重复使用引理6.3，最后可得所求的匹配M1，……，Mp 。 注 在实际应用中，教师和班级往往会提出一些，例如所上节次，的要求，问题变得很复杂。Even，Itai & Shmir（1976）证明：在教师和班级提出条件时，判定课表的存在性问题是个NP-complete问题。甚至当G为简单偶图，且学生不提出要求的情况下，也是如此。 lllpp集和团 集 定理7.1 S为图G的集 V\\S 为G的覆盖。 证明：S为集 不存在两端全在S中的边 G的每边至少有一端在V\\S 中 V\\S为G 的覆盖。 # S V为G的 团（clique） G[S]为一完全图。 数（independent number）G 最大集的元素个数。 覆盖数（coering number）G G的最小覆盖的元素个数。 推论7.1 。 证明：设S为G的最大集，则V\\S为其覆盖，因此 |V\\S |= - 。 又，设K为G的最小覆盖，则V\\K为其集，因此 |V\\K| = - 。 ∴ 。 # 33 注 由上述证明知 S为G的最大集 V\\S为G的最小覆盖 。 顶点着色 色数 正常（顶点）着色（proper （vertex） coluring） 每边两端不同色。 k-（顶点）着色（k-（Vertex）colouring） k种色在V(G)上的一种分配，且任二相邻（的不同）顶点不同色。 V的一个k-划分（V1，……，Vk）使每个Vi（可为）都是G的一个 集。 k-（顶点）可着色（k-（vertex） colourable） G有一k-着色。 显然， G为k-可着色 G的基础简单图为k-可着色。 由此，我们约定 本章只讨论简单图。 例。 G为1-可着色的 G 为一空图。 G为k-可着色的 G 为k-部图。 G为k-可着色的 G为j-可着色的（k j）。 色数（chromatic number） (G) = { k G为k-可着色的} 。 G为k-色图 (G) = k。 G为临界的（crtical） (H) < (G) H G 。 G连通且满足 (G-e) < (G) e E(G) 。 G为k-临界的 G为临界图，且 (G) = k。 显然，G为k-色图 G包含一k-临界子图。 例。1-临界图 K1 （唯一）。 2-临界图 K2 （唯一）。 3-临界图 奇圈 。 4-临界图 例如：K4 ，Grotzsch图等。 注意 一图G的临界图不一定是它的导出子图。 定理8.1 G为k-临界图 k - 1 。 证明：反证，假设 < k-1 。取v V使d(v) = 。因G 为k-临界图的，G-v必是（k-1）-可着色的。令 Grotzsch图 （ V1，……，Vk-1） 为G-v 的(k-1)-着色。由于d(v) = < k-1，v一定与某一Vj中所有顶点都不相邻。从而 （ V1，……，Vj{v}，……，Vk-1） 是G的(k-1)-着色，于是(G) k - 1 ，矛盾。 # 推论8.1.1 (G) = k G中至少有k个度 k-1 的顶点。 证明：令H为G的k-临界子图。由定理8.1知 dH(v) (H) k-1 v V(H) 。 ∴ dG(v) dH(v) k-1 v V(H) 。 又因H为k-色的，必有 |V(H)| k 。 # 推论8.1.2 对任一图G都有 + 1 。 证明：由推论8.1.1知 - 1 。 # 令S为连通图G的一个点割。 V1，……，Vn为G - S 的各分支的顶点集。称 34 Gi = G[ViS] 为G的S分支。称G1，……，Gn上的各个着色在S上是一致的，当且仅当在各个着色中S中每顶点都被着以相同的色。 定理8.2 临界图的任一点割都不是团。 证明：反证，假设k-临界图G有一点割S是团。令G1，……，Gn是G的S分支。因G为k-临界的，每个Gi都必是（k-1）-可着色的。但S为团，每个Gi的任一（k-1）-着色都导致S中所有顶点彼此不同色。从而一定存在G1，……，Gn在S上一致的（k-1）-着色。这些着色一起构成G的一个（k-1）-着色，矛盾。 # 推论8.2 每一临界图是一个块。 证明：若v是一割点，则{v}是一个点割，且是团。故临界图不含割点，因而是个块。# 注 NP-complete prob. ： 对任给图G及正整数k |V| ，G是否为k-可着色的？ 从而，求任给图G的色数是个NP-hard prob. 。 贪心（greedy）着色法 ：用色1，2，… 逐步（按某一 顶点排序）一个个顶点进行着色，每次选用尽可能小的颜色进行着色。 例如，对任给图G，按任一顺序进行贪心着色，易见，至多用了 + 1 个色，从而得到了推论8.1.2另一证明。 显然，贪心着色法所用的颜色数完全取决于着色的顺序，即顶点的一个排序。假如我们事先知道图G的一个-着色为 C = （E1，E2，……，E ） 。 按E1，E2，……，E任作一顶点排序（同一色集Ei内随意排序），按此顺序进行贪心着色，易见，一定恰好用了 个色。因此，设法构想一适当的顶点排序进行贪心着色，往往可能得到关于着色的一个较好结果（如Brooks定理之证明）。下面是这方面的一些结果： 例。设图G 中度序列满足：d1 …… d ，则 maxmin{di1,i} 。 i证明：不妨设顶点排序 ：v1，……，v 恰使d(vi ) = d i i=1,2,..., 。沿 进行贪心着色。 设vk被着上了色 。易见，它一定与前面 -1个不同色的顶点相邻，因此 dk＝ d(vk) - 1 。 又，显然 ｋ 。 ∴ min {dk + 1，k} 得证。 # 例。试证：(G) 1+ max{ (H) | H为G的导出子图}。 证明：作G的顶点排序 ：v1，……，v 如下： v 为图G的最小度顶点； v-1 为图G-v 的最小度顶点； v 为图G-{v，v-1} 的最小度顶点； ……………… 令L = max{ (H) | H为G的导出子图}。注意到G，G-v ，G-{v，v-1} ，…都是G 的导出子图。从而，每个dH(vi) L，于是每个vi 都只与前面 L个顶点相邻。因此贪心着色法至多用了L+1个色。故 (G) 1+L = 1+ max{ (H) | H为G的导出子图} 。 # 注 顶点着色问题的另一常用技巧是基于以下显而易见的命题： 设d(u) k-2 (k 2) u U V，而G-U为k-可着色的，则G也是k-可着色的。 例。试证 (G)+(Gc) = +1。 证明：对 进行归纳。当 2时，显然成立。假设对顶点数< 时都成立，而(G)= 。 情况1 当(G) (G)-1时：则 c (G)= -1-(G) - (G) 。 cc (G) (G)+ 1 -(G)+1，得证。 情况2 当(G) < (G)-1时：取u使 dG(u) = (G) (G) -2 。 35 因此，首先有 (G1) = (G) 。 其中G1=G - u 。由归纳假设知， (G1) + (G1c) = 。 ∴ (G)+(Gc) = (G1)+(Gc) (G1)+(G1c) +1 = +1。 # 习题 8.1.1. 证明：若C =（E1，E2，……，E ）是图G的一个-着色，则任二Ei与Ej间至少有一边相连。 8.1.2. 证明：若G的任二奇圈都有公共顶点，则 5 。 8.1.3. 证明： 设图G 中度序列满足：d1 …… d ，则 maxmin{di1,i} 。 i8.1.4. 利用习题8.1.3 证明： (a) 2 。 (b) (G)+(Gc) = +1。 (c) 推论8.1.1 。 8.1.5. 试证：(G) 1+ max{ (H) | H为G的导出子图}。 8.1.6.* 设k-色图G上有这样一个正常着色（不一定为k-着色），其中每种色都至少分配给两个顶点。证明：G也有这样的k-着色 。 8.1.7. 证明：若G 是简单图，则 2/(2 - 2 ) . 8.1.8. 若G 的任二k-着色都导出V的相同的k-划分，则称G为唯一k-可着色的。 8.1.9. 证明：k-临界图没有顶点割能导出唯一(k-1)-可着色子图。 8.1.10, (a) 证明：若u，v为临界图的二顶点，则不可能有N(u) N(v) 。 (b) 试证：不存在恰有k+1个顶点的k-临界图。 8.1.11. (a) (G1G2) = (G1) +(G2) ，其中G1G2 称为图G1与G2的联图，它是将 它们间的每对顶点都用新边连起来所得的图。 (b) G1G2是临界图，当且仅当G1与G2都是临界图。 8.1.12. 设G1与G2是恰有一公共顶点v的k-临界图，且vx和vy 分别是G1和G2的边， 则 (G1-vx)(G2-vy)+xy也是k-临界图。 8.1.13. 对 n = 4及 n 6 构造n个顶点的4-临界图。 8.1.14.* (a) 设V的2-划分（X，Y）使G[X]和G[Y]都是n-可着色的，且边 割 [X，Y] 最多有n-1条边，则G也是n-可着色的。 (b) 试证：每个k-临界图都是(k-1)-连通的。 Brooks 定理 定理8.4 设简单连通图G既为非奇圈、亦为非完全图，则 。 证明：对 进行归纳。当 3时，显然成立。假设当 < n时都成立，而(G) = n。不妨设：① G为-正则的。（不然，取u使d(u)= < ，由归纳假设，易见，G - u为 -可着色的，从而G亦然。） ② G为2-连通的。（不然，令v为G的割点，则存在E的2-划分（E1，E2）使G[E1]与G[E2]恰有一公共顶点v，从而易见，结论成立。）③ 3。（不然，G为圈，结论成立。） 今选取3个点 x1 ，x2，xn 如下： 若 3，则任取一点为xn ，并取N(xn）中任二不相邻顶点作为 x1 与x2 。（ 这样的二顶点一定存在。不然，N(xn） {xn} 是一团，从而G是完全图，矛盾。） 若 = 2，则选取xn使 (G - xn )= 1。注意到G - xn中至少有2个endklocks （即，只含G的一个割点的G的块），每个至少含一G的非割点与xn 相邻接。取不在同一endklock中的两个这种顶点作为x1 与x2 。 36 在上述两种情况下，我们都有 G - {x1, x2} 连通； 且 xnx1 ， xnx1 E(G) 而x1x2 E(G) 。 下面我们来作V的一个排序： 取xn-1 V \\{x1, x2, xn}; 取xn-2 V \\{x1, x2, xn-1, }; ................................. 由于G - {x1， x2}之连通性，上述步骤可一直进行到底。得V的一个排序： x1， x2，……，xn 。 其中每个xi （i < n )都至少与某xj ，j > i，相邻接。又，x1 与x2不相邻。于是，贪心着色法只用了 个色。 # 习题 8.2.1. 证明Brooks定理等价于下述命题：若G是k-临界图（k 4），且不是完全图，则2 (k-1)+1 。 8.2.2. 利用Brooks定理证明：若G是 = 3的无环图，则 4。 围长和色数 易见，若G中最大团的顶点数k，则 k。下面的定理表明，一个有很大色数的图，其最大团的顶点数不一定也很大。 定理8.7 对任正整数k，都存在不含K3的图G使 (G) = k 。 (即，可找到色数任意大的图，但其最大团顶点数却只为2。） 证明：对k进行归纳。当k = 1时，G1 = K1满足要求；当k = 2时，G2 = K2 也满足要求；一般，设Gk = (Vk , Ek ) ，Vk = {v1，……，vn）满足要求（k 2） ，则构造 Gk+1 = (Vk +1, Ek+1 )如下：令 Vk+1 = Vk {u1，……，un} {v}。 其中 u1，……，un，v 为新加的顶点。将每个u i 与N(vi)中每个顶点用新边连起来；再将u与每个ui 也都新边连起来，所得图即为Gk+1 。 易见，Gk+1中不含K3。又，Gk的任一k-着色可扩充成Gk+1的（k+1）-着色如下：将每个ui着以vi 上的色；再用一新色着在v上。显然，这是Gk+1的正常（k+1）-着色，从而Gk+1是（k+1）-可着色的。余下只要再证Gk+1不是k-可着色的即可：不然，不妨设在该k-着色中v被着以色k。这时无一ui被着以色k。今，将每个被着以色k的顶点vi都改着以顶点ui的色。易见，这是Gk+1的正常k-着色。它导致Gk的一个正常（k-1）-着色，这与Gk为k色图相矛盾。 # 注 Hajos曾提出似乎是可信的猜想： G为k-色图 G包含Kk的一个剖分。 当k=3及4时可证猜想成立。但1986年已证明该猜想不成立。 习题 8.3.1. 证明：定理8.7中的图Gk是一k-临界图。 8.3.2*(a) 设G是围长至少为6的k-色图（k 2）。作一新图H如下：取k个新顶点集S及G的k 个互不相交的拷贝，且建立G的拷贝与S的个顶点的一一对应。再将G的每个拷贝与它在S中相对应 的个顶点之间用一匹配连接起来。证明：H的色数至少为k+1，其围长至少6。 (b) 试证：对任k 2，都存在围长为6的k-色图。 37 平面图 平图和平面图 图G可嵌入（embededable）于平面中 G可画在平面上，使它的边只在端点处才可能相交叉。 （该画法称为G的一个平面嵌入（planar embedding）或平图 （plane graph）） G为平面图（planar graph） 例。K5，K3,3 以及它们的剖分都是非平面图。它们中任一个去掉任一边后都是平面图。 注意 平面图和平图间的区别。后者是前者的一个几何实现（具体画法）。 Jordan 曲线定理 平面中任一Jordan 曲线J（连续不自交的闭曲线），将余下的平面划分成二不相交开集：J的内部（interior）和 J的外部（exterior），分别记为 int J和ext J。（它们的闭包分别记为Int J 和 Ext J）。连接int J中一点到ext J中一点的任一条曲线一定与J交于某一点。 定理9.1 K5为非平面图。 证明：反证，假设G为K5的一个平图。令G的五个顶点为v1，……，v5。注意到圈 C = v1v2v3v1 为平面上的一条Jordan 曲线，且v4必在int C 或ext C中。若v4 int C，则边v4v1， v4v2，与v4v3将int C划分成三个区域int C1，int C2，和int C3。 这时v5一定在上述三个区域及区域ext C之一。若v5 ext C，则因v4 int C，边v4v5 必与C交于某一点，这与G为平面图的假设相矛盾。其它情形类似地也导致矛盾。 # 定理9.2.’ K3,3为非平面图。 证明：类似，略。 平面嵌入的慨念可推广到其它平面上。称 图G可嵌入于曲面S上 G可画在S上，使它的边仅在端点处才可能相交叉。 例。K5和K3,3都可嵌入于环面上； K3,3可嵌入于Mobius带上；每个图都可“嵌入”于三维空间R3中。 定理9.2 G可嵌入于平面上 G可嵌入于球面上。 证明：利用球极平面射影，略。 # 对偶图 平图G的面（face） G将平面划分出来的连通区域的闭包。 外部面（exterior face） G中唯一的无界面。 定理9.3. 对平面图G 的任一顶点，都存在G的一个平面嵌入，使它在该嵌入的外部面上。 38 证明： 先将G嵌入于球面上，并将球面的北极放在含该顶点的G的一个面中，再利用球极平面射影。 # v1记号 F(G) = 平图G的面的集合。 f5e6 (G) = 平图G的面数。 v7e1f3e7ee4 b(f) = 面f的周界。 9当G连通时，b(f)可当作一闭途径，其中G在b(f)f4v2f1v6eev4中的每一割边在该途径中都恰被走过两次。当G为2-58连通时，b(f) 为一圈。 f2e2e3例。 b(f1) = v3v1e1v2e5v4e8v6e9v6e8v4e4v1e6v7e7v7e6v1 。 b(f5) = v1e1v2e2v3e3v4e4v1 。 在平图G中面f与它的周界上的边和顶点相关联。称G的一边e分隔（seperate）与它相关联的面。易见， e为G的割边 e只与G的一个面相关联 e恰分隔G的一个面。 e为G的非割边 e恰与G的两个面相关联 e恰分隔G的两个面。 平图G中面f的度（degree） dG(f) = 与面f 相关联的边数（割边记为2）。 例如，d(f1) = 9。 平图G的对偶图（dual graph）G*是这样的一个图：它们之间有如下的一一对应关系 e4e3 G的面f G*的顶点f* ； e1 G的边e G*的边e* 。 e2fe5f1且 f2e84** * * f G的顶点f1与f2被边e连接 3e7f5e6 G的面f1与f2 被边e 分隔。 * ** 例如，左面所示平图G的对偶图G= (V , E) 为 V* = {f1*，……，f5*} ， E* = {e1* = f1*f5* ， e2* =f5*f5* ，e3* = f2*f5* ，……，e8* = f2*f3*} 。 易见，平图G的对偶图G*是一平面图，事e4e3* 实上存在G 的一个平面嵌入（称为几何对偶） e1e2如下：在G的每个面f中放置顶点f*，对应于Gf1e5ff2e84* 的每一边e，画一条边e使它穿过e恰好一次（且f3e7不穿过G的其它边）。例如，上例平图G的对偶fe65图G* 如右图所示。 由上述知，G* 一定是连通平面图。且有 e是G的环 e* 是G* 的割边。 ** e是G的割边 e 是G 的环。 有时，为方便计，把平图G的几何对偶G* 当作G的对偶图。这时，若G连通，则有 G** = (G* )* G。 （当G不连通时，上式不一定成立）。 注意 “平图G H G* H* ”不一定成立。 例如，右边二平图是同构的，但它们的对偶图并不同构。因此，对偶图的概念只对平图有意义，不能推广到平面图上。 由G* 的定义易知： (G* ) = (G) * (G) = (G) dG*fdf fFG *G定理9.4 设G为平图，则 39 d(f)2 fFG***fV(G) 证明：左式d(f*)2(G*)2(G) 。 # 习题 9.2.1 .(a)证明：图G是平面图 G的每个块都是平面图。 (b)试证：极小非平面图是简单块。 9.2.2. 若一平图和它的对偶图同构，则称该平图为自对偶的。 (a) 若G为自对偶的，则 = 2 - 2 。 (b) 对每个 n 4 ，找出n顶点的自对偶平图 。 9.2.3. (a) 证明：B是平图G的键 { e* E(G* ) | e B } 是G* 的圈。 (b) 证明：C是平图G的圈 { e* E(G* ) | e C } 是G* 的键。 (c) 试证：Euler平图的对偶图是偶图。 9.2.4. 设G是平图，证明： (a) (G* )* G G是连通图。 (b) (G** ) = (G) 。 9.2.5. 设T是连通平图G的生成树，E* = {e*E(G*)eE(T)}。证明：T* = G*[E*] 是G* 的 生成树。 9.2.6. 每个面的度都是3的平图称为平面三角剖分图。证明：每个 3的简单平图都是某简单平面三角剖分图的生成子图。 9.2.7. 设G是 4的简单平面三角剖分图，证明：G*是简单2-边连通3-正则平面图。 9.2.8.* 证明：任何平面三角剖分图，都包含一个有2 (G)/3条边的偶子图。 Euler 公式 定理9.5 (Euler) 设G为连通平图，则 - + = 2 。 证明：对 进行归纳。当 = 1时，G的每边为割边（因每边只分隔一个面）。又因G连通，从而G是树（定理2.4)，于是 = - 1，定理成立。 假设定理对 < n成立，而(G) = n 2。任取G的一条非割边e（它一定存在，不然导致 = 1，矛盾）。注意到e分隔G的两个面，有 (G-e) = n-1 。 （e所分隔的G的两个面，在G - e 中合而为一）。因此由归纳假设有 (G - e) - (G - e) + (G - e) = 2 。 但 (G - e) = (G)；(G - e) = (G) - 1； (G - e) = (G) - 1 ，将它们代人上式，得证。 # 推论9.5.1 对平图G的任二平面嵌入H及R都有 (H) = (R) 。 证明：因 H R，它们的顶点数及边数都相等。再由本定理，得证。 # 推论9.5.2 当 3时，若G为简单平面图，则 3 - 6 。 证明：不妨设G为连通图。由于G为简单图， d(f) 3 f F。 再由定理9.4得 2 = d(f) 3 = 3( - + 2) 。 fF从而得证。 # 推论9.5.3 设G为简单平面图，则 5 。 40 证明： 当 2时显然成立。当 3时，由定理1.1及推论9.5.2有 d(v) = 2 6 - 12 < 6 ， vV ∴ 5 。 # 推论9.5.4 K5 为非平面图。 证明：若K5 为平面图，则推论9.5.2得 10 = 3*5 - 6 = 9 ， 矛盾。 # 推论9.5.5 K3，3 为非平面图。 证明：若K3，3 为平面图，由于它的每个圈长 4，它的每个面的度 4。因此 4 d(f) = 2 = 18 ， fF 4。 ∴ 2 = - + 6 - 9 + 4 = 1 ， 矛盾。 # 习题 9.3.1. (a) 证明：若G是围长k 3的连通平面图，则 k( - 2)/(k - 2) (b) 利用(a)证明： Petersen图是非平面图。 9.3.2. 证明：每个平面图都是6顶点可着色的。 9.3.3. (a) 证明：若G是 11的简单平面图，则Gc 是非平面图。 (b) 找出一个 = 8的简单平面图，使Gc 也是平面图。 9.3.4. 若G可表示为若干个平面图的并图，称这种平面图的最小个数为G的厚度，记为(G)。于是， (G) = 1 G是平面图。 (a) 证明：(G) { /（3 - 6）}； (b) 试证：(K) {( - 1)/6( - 2)} ，并利用习题9.3.3(b)证明，等式对所 有 8成立。 9.3.5. 利用习题9.2.5.的结果推导Euler公式。 9.3.6. 证明：若G是平面三角剖分图，则 = 3 - 6。 9.3.7. 设S是平面上n 3个点的集合，其中任二点间的距离 1。证明：最多有 3n - 6个点对其距离恰为1。 Kuratowski 定理 下面的两个引理是显然的： 引理9.10.1 G为非平面图 G的每个剖分图为非平面图。 引理9.10.2 G为平面图 G的每个子图为平面图。 定理9.10 (Kuratowski,1930) G为平面图 G不包含K5 或K3，3的剖分。 证明：略。 Wagner定理 G为非平面图 G包含可压缩（contractible）成K5或K3，3的一个子图。 （证明：略。） （一个简单图G的初等压缩（elementary contraction）是将G的一边uv去掉，并将顶点u和v合并成一个新顶点。图G可压缩成图H，是指G可经过一系列的初等压缩而变成H。） 例。Petersen图是非平面图。因它包含K3，3的一个剖分；它也可压缩成K5 。 41 五色定理和四色猜想 定理9.11 (Headwood,10) 每个平面图是5-（顶点）可着色的。 证明：反证，假设定理不成立。令图G为最小反例。易见，G为简单连通图且 6。选取一顶点u使d(u) = 。由推论9.5.3.知， 5。由对G的假设知，G - u上可进行正常5-着色 （V1，……，V5）。 当u只与 4个顶点相邻时，显然，G为5-可着色的，矛盾。因此u必恰与5个顶点相邻。不妨设它们按顺时针顺序为v1，……，v5 ，且每个vi Vi 。记 Gij = G[Vi Vj] i j， 1 i，j 5。 如果存在i，j使vi与vj不在Gij同一分支中。则将Gij中含vi的分支上的色i与j对换，得G - u 的一个新的5-着色，其中u只与4种色相邻，从而G为5-可着色的，矛盾。因此，每个Gij中都有一（vi ，vj）-路Pij ，由色i和j顶点交错组成。令圈 C = uv1P13v3u 。 由于C分隔v2和v4，由Jordan曲线定理，P24一定与C交于一点。由于G为平面图，这一点只能是G的顶点。但 P24上只有色2和4，而C上无此二色，这是不可能的，矛盾。# 4-色猜想（four colour conjecture） 所有（无环）平面图都是4-顶点可着色的。 平图G的k-面着色（k-face colouring） k种色在G的所有面的一个分配（不一定是正常着色） 平图G为k-面可着色的 G有一正常的k-面着色。 面色数（face chromatic number） *(G) = min{k | G为k-面可着色的} 。 显然，对任一平图G都有 *(G) = (G* ) 。 定理9.12 以下诸命题是等价的： ① 每一平面图是4-（顶点）可着色的； ② 每一平图是4-面可着色的； ③ 每一简单、2-边连通、3-正则、平面图是3-边可着色的。 证明：① ② ： 显然。 ② ③ ： 设G为简单、2-边连通、3-正则、平面图；G为其平面嵌入。由②G为4-面可着色的。用摸2整数域上的向量 c0 = (0,0)，c1 = (0,1)，c2 = (1,0)，c3 = (1,1) 表示该4个色。今对G 进行边着色如下：将G的每边着以被它所分隔的两个面的色的和。 （设与顶点v相关联的3个面上的色为ci，cj，ck。则与顶点v相关联的3条边上的色为ci+cj，cj+ck，ck+ci。） 因G的每边恰分隔两个不同的面（∵其每边为非割边），因此没有一边被着以色c0 ，从而上述边着色是一3-边着色。又，易见，关联于每个顶点的3条边被着以不同色 。因此上述边着色是正常3-边着色。 ③ ① ：反证，假设①不成立，则存在简单平面图G使 (G) = 5。令G为其平面嵌入。由习题9.2.6及9.2.7知，G为某简单平面三角剖分图H的生成子图；且H的几何对偶H* 是简单、2-边连通、3-正则平图。于是我们可得以下之 断言 H* 是4-面可着色的。 由上述断言得： 5 = (G) (H) = *(H* ) 4 , 矛盾，从而定理得证。 下面来证断言： 由③知，H* 有一正常3-边着色 （E1，E2，E3）。 *易见，每个Ei 是H 的一个完美匹配。令 Hij* = H*[Ei Ej] i j ， 42 ~~~~~~~ 则Hij* 是一些不相交圈的并。从而，易见，Hij* 是2-面可着色的。 注意到，H* 的每个面一定包含在H12* 的一个面及H23* 的一个面的交中。由H12*及H23* 上的2-面着色，可得H* 的4-面着色如下： 将每个H* 的每个面f ，着以包含f 的H12* 的面上的色 12（=0，1） 及包含f 的H23* 的面上的色23 （=0，1）组成的色对（12，23 ）。易见，这4-面着色是正常的。（设H* 的两个面f及f’有公共边e，每个面上的色分别为（12，23）及（‘12，‘23）。则，例如，当e E1时，必有 12 ‘12 ，从而f及f’有不同色。） # 习题 9.5.1. 证明：2-边连通图G是2-面可着色的当且仅当G是Euler图 。 9.5.2.* 证明：平面三角剖分图G是3顶点可着色的当且仅当G是Euler图 。 9.5.3. 证明：每个Hamilton平图都是4-面可着色的。 9.5.4. 证明：每个Hamilton3-正则图都有Tait着色（即，3正则图的正常3-边着色）。 9.5.5. 按③ ② ① ③的顺序证明定理9.12。 G1v1u1u2G2v2 9.5.6. 设G是 = 2的3-正则图。 (a) 证明：存在G的子图G1和G2及不相邻的顶点对u1 ,v1 V(G1) 和 u2 ,v2 V(G2)，使得G由图G1和图G2 以及在顶点u1,v1,u2,v2上由‘梯子’连接的图所组成。 (b) 证明：若G1 + u1v1 和G2 + u2v2 都有Tait着色，则G也有Tait着色。 (c) 根据定理9.12证明：四色猜想等价于Tait猜想，即每个简单3-正则、3-连通、平面图都有Tait着色。 9.5.7. 给出满足下列条件的例子各一个： (a) 不具有Tait着色的3-正则平面图； (b) 不具有Tait着色的3-正则、2-连通图。 平面性算法 设H为G（不一定为平面图）的真子图，称（边导出）子图B为G相对于桥（bridge），如果 ① B为边uv， u,v V(H) ，且 uv E(G)\\E(H) 。 ② B为 G - V(H) 的一个分支，以及G中V(H)与该分支之间的连接边，所组成的子图。 易见，若B为H的一个桥，则 ① B为连通图； ② 对B中任二顶点x与y，B中存在一(x, y)-路内部不交于H。 称V(B) V(H)为接触顶点(vertices of attachment)。当G连通时，每个桥至少有一个接触顶点。 设H为G的平面子图，称其 平面嵌入H为G-可容许的（G-admissible） ~ 例。 称H的桥B可画（drawable） G为平面图，且存在G的平面嵌入G ~~H 。 G~H ：G可容许的 非G-可容许的 在H的一个面f中 B对于H的接触顶点全包含在f的周界上。 43 ~记号 F(B,H ) = 使B可画于其中的H的面的集合。 定理9.4 若H 为G可容许的，则对H的任一桥B都有 F(B,H ) 。 ~~ ~~证明：由定义，存在G的平面嵌入G ~F(B,H ) 。 # 显然， G为平面图 G的基础简单图的每个块都是平面图。因此，平面性问题只须考虑简单块之情形。 以下算法对简单块G求出其平面子图的增序列G1，G2，……及其平面嵌入G1，G2，……。当G为平面图时，每个Gi为G可容许的，且G1，G2，…… 终止于G的一个平面嵌入。 平面性算法（Demoucron，Malgrange & Pertuiset 19） ~~~~H 。B所对应的G的子图必画在H的一个面中，故 ~~~~~~(1). 令G1为G的一个圈。求G1的一个 平面嵌入G1 。令 i = 1。 ~(2). 若E(G)\\E(G1) = ，停止（完毕，得G ）。否则，找出G中Gi的所有桥，并对每个桥求出集 ~合F(B,Gi ) 。 ~(3). 若存在B使 F(B,Gi ) = ，停止（由定理9.14，G为非平面图）。若存在B使 ~~~|F(B,Gi)| = 1，取f为 F(B,Gi ) 中的面；否则，任取一桥B，并且取 F(B,Gi )中任一面为f。 ~(4) 选一连接B对Gi的二接触顶点的路Pi B。令 Gi+1 = Gi Pi。通过把Pi 画在 Gi 的面f ~中，得 Gi+1 的平面嵌入Gi+1 。 算法证明大意 只要再证对平面图G算法不会停止于(3)。由定理9.14，只要证明算法求出的 G1，G2，…… 为G可容许的即可。 ~~ G1 显然是G可容许的。设G1，……，Gk 为G可容许的，来证Gk+1 也是G可容许的。由定义知，存在G的平面嵌入G Gk。令B，f为(3)中所取的桥和面。 ① 若在G中B恰好画在f中（ 当|F(B,Gk) | = 1时，必是此情形 ）：由(4)知，Gk+1 为G可容许的。 ~~~~~~~~~~~~有 |F(B,Gk) | 2 。因此总可将G 中被画在f中的桥 与被画在f′中② 若在G中B被画在 Gk 的另一面f′中： 这时的所有桥B都~f′的桥 通过公共周界进行交换，得G的另一平面嵌入，其中B恰好被画在f中，得前面的情形① 。 例。判定以下二图的平面性： f 1. 块中找一个圈G1。 2. 在G中确定Gi的所有桥及它们对Gi的接触顶点。 3. 对的每个面f确定b(f)。 4. 对每个桥B确定F(B, Gi ) 。 5. 在Gi的某个桥B中，找连接其二接触顶点的路P。 算法中要进行的运算为： ~44 上述1. ~ 5. 都有好算法，因此平面性算法是好算法。 习题 9.6.1. 用本节的算法证明Petersen图是非平面图。 有向图 有向图 有向图（directed graph；digraph） D = （V，A）： V(D) —— 顶点集。 uv A(D) —— 弧集。 弧a = (u,v) ：其头为 v，其尾为u；弧a从u连到（join to）v。 有向子图（subdigraph）。 有向图D的基础图（underlying graph） 对应于D的无向图G。 （称D为G的一个定向（orientation）图。） （无向）图的每个慨念，在有向图中仍然有效。 r s例如，右图是2-连通图；有Hamiton 圈；有完美匹配； = = 3；vrswu是它的一条(v,u)-路；vyzwsrv是它的一个圈，等等。此外，有向图还有一些与方向有关的慨念，如有向途径 ve（directed walk）、有向迹（directed trail）、有向路（directed e51xwpath）、有向Euler环游（direted Euler tour）、有向圈（directed ucycle）等等。例如上右图中， e2e4 (v,e1,x,e2,y,e3,z,e4,w.e5,u) 为一 有向（v,u)-路， e3可简记为 （v,x,y,z,w,u) ； y z (y,z,w,s,r,x,y) 为一 有向圈。 称顶点v从u可达的（reachable from u） 存在有向（u，v）-路。 称顶点u与v为双向连通的（diconnected；strongly connected） u与v彼此可达的。 易见，双向连通性是V上的一个等价关系，它的等价类确定了V的一个划分（V1，……，Vm)，使 顶点u与v双向连通 u与v 同属某等价类Vi 。 称每个导出子图D[V1]，……，D[Vm]为有向图D的一个双向分支（dicomponent；strong component）。当D只有一个双向分支时，称D为双向连通的。易见，任二双向分支之间的弧都是一个方向的。 例。 D的双向分支 有向图D 入度（indegree） dD(v) 。 出度（outdegree） dD(v) 。 - 记号 +， ：最小出、入度； + ， ：最大出、入度。 称有向图D为严格的（strict） 45 无环、且无二弧其端点及方向相同。 习题 10.1.1. 一个简单图有多少个定向图？ 10.1.2. 证明： dvV(v) = = dvV(v) 。 10.1.3. 设有向图D中无有向圈，则 (a) = 0 ； (b) 存在一个顶点排序v1，……，v ，使对1 i ，每条以vi为头的弧其尾都在{v1，……，vi-1} 中。 10.1.4. 证明：D是双向连通的 D是连通的，且D的每个块是双向连通的。 10.1.5. D的逆图D 是把D中每弧的方向都改为其反向所得的有向图。试用逆图慨念及习题 10.1.3.(a) 来证明： 若有向图D中无有向圈，则+ = 0 。 10.1.6. 证明：严格有向图包含长 max{ ，+}的有向路。 10.1.7. 证明：严格有向图中若max{ ，+} = k 1，则D包含长 k+1 的有向圈。 10.1.8. 设 矩阵A = [aij ]为有向图D的邻接矩阵，其中aij 是D中以vi为尾、以vj为头的弧数。证明：Ak的第(i,j)元素是D中长为k的（vi ,vj)-有向途径的数目。 10.1.9. 设D1，……，Dm为D的双向分支。D的凝聚图H是一有m个顶点w1，……，wm的有向图。H中存在以wi为尾、以wj为头的弧，当且仅当D中存在尾在Di 、而头在Dj中的弧。证明：H中不包含有向圈。 10.1.10. 证明：任一图G都有一个定向图D，使对每个顶点v都有|d+(v) - d-(v)| 1。 有向路 易见，有向图中最长路的长和最长有向路的长之间并无任何密切的关系，例如下面的有向图最长路的长为 （可任意大） ，而最长有向路的长为1。 定理10.1 (Roy,1967; Gallai,1968) 有向图D包含一长为 - 1 的有向路。 证明：令D 为D的极大无有向圈、有向生成子图（注：D 可由空生成子图作为开始，在保持无有向圈的条件下，通过逐步加弧而得） 。令k为D 中最长有向路的长。今用色1，2，……，k+1对D 进行顶点着色如下： 将v着以色i D 中以v为起点的最长有向路的长为i - 1 。 来证这是D的正常(k+1)-顶点着色： 先证，D 中任一有向(u,v)-路P的起、终点u与v一定不同色：设v被着以色i 。则由着色法知，在 D 中以v为起点的一最长有向路，设为，Q的长为i - 1 。由于D 中无有向圈，PQ为一有向路，起点为u，长 i 。从而u上的色j > i。 只要再证，D中任一弧(u,v)的两端一定不同色：当 (u,v)为D 中的弧时，它就是D 中的一有向(u,v)-路，从而u与v不同色。当 (u,v)不是D 中的弧时，由D 之极大性知 D + (u,v) 包含一有向圈C。于是， C - (u,v) 是 D中的有向(v,u)-路，从而u与v也不同色。 由上述知，D为(k+1)-可着色的，因此 k+1 ，得k - 1 ，故D中有长为 - 1 的有向路。 # 注 定理10.1在如下意义下是最佳的： 46 对每个（无向）图G，都存在G的一个定向图，其最长有向路的长恰为 - 1。 证明：令 （V1，……，V-1） 为G的正常 -顶点着色。今作G的定向图D如下： 边uv（不妨设， u Vi ，v Vj）定向为弧 (u,v) i < j 。 显然，D中不含长 > - 1的有向路。再由定理10.1得证。 # 称完全图的定向图为竞赛图（tournament） 推论10.1 (Redei,1934) 每个竞赛图都有一Hamilton 路。 证明：注意到 = 即可。 # 设(u,v)为有向图D中的一弧，则称u为v的内邻点（in-neighbour）；称v为u的外邻点（out-neighbour）。记 ND(v) 和 ND(v) 分别为有向图D中顶点v的内邻集和外邻集。 定理10.2 (Chavtal & Lavasz,1974) 无环有向图D包含一集S，使D中的每个不在S中顶点，都是从S中某顶点通过长 2的有向路可达的。 证明：对 进行归纳。当 = 1时，显然成立。假设定理对顶点数 < 成立，而D的顶点数 = （ 2）。任取D的一顶点v，由归纳假设知 D’ =D -（ND(v) {v}） 中有一集S’，使D’中的每个不在S’中顶点，都是从S’中某顶点通过长 2的有向路可达的。在D中， ① 若v是S’中一顶点u的外邻点：则在D中，ND(v)的每个顶点都可从u用长 = 2的有向路可达的，因此取S = S’即可满足要求。 ② 若v不是S’中任一顶点u的外邻点，则 S’中顶点都与v不相邻，这时集 S = S’ {v}满足要求。 # 推论10.2 每一竞赛图都包含一顶点，使其它顶点都是从它用长 2的有向路可达的。 证明：注意到 1 即可。 # 习题 10.2.1. 证明：每个竞赛图或者是双向连通的，或者是只要将其中某一弧改向就可变成双向连通的。 10.2.2.* 称有向图D是单连的（unilateral），当且仅当对于D中任二顶点u和v，或者v是从u可达的，或者u是从v可达的。证明：D是单连的当且仅当D有一条生成有向途径。 10.2.3.(a) 设P = （v1，……，vk）是竞赛图D中的一条极大有向路。如果P不是有向Hamilton 路，而v是不在P上的任一顶点，证明：存在某个i，使(vI, v)和(v, vI+1)都是D的弧。 (b) 证明：Redei定理。 10.2.4. 通过考察最大出度顶点来证明推论10.2。 10.2.5* (a) 设D是 > mn的有向图，而f是定义在V上的一个实函数。证明：D中或者存在一有向路(u0，u1，……，um) 满足f(u0) f(u1) …… f(um)；或者存在一有向路 (v0，v1，……，vn) 满足f(v0)>f(v1)>……>f(vn) 。 (b) 试证：任意mn+1个不同整数的序列中，或者包含一个m项的递增子序列；或者包含一个n项的递减子序列 10.2.6.(a) 利用定理10.1和推论8.1.2证明：G有一个定向图，它的最长有向路的 长 。 (b) 给出(a)的构造性证明。 圈 记号 （S，T）是D中尾在S内而头在T内的所有弧的集合。（S，T是V的子集） 47 定理10.3 (Moon,1966) 3的双向连通竞赛图D中，每个顶点包含在一有向k-圈中，3 k 。 证明：设u是D的任一顶点。用对k的归纳法来证明。当 k =3时， 令S = N+(u) ， T = N-(u) 。由D的双向连通性知， S，T，（S，T） 都是非空的。 因此D中存在一弧(v, w) 使v S，w T 。从而u在有N+(u)v向3-圈 (u,v,w,u) 中，结论成立。 u假设对每一k，3 k n < ，u都在有向k圈中，来 证u也在有向（n+1)-圈中：令 N-(u) C = （v0，v1，……，vn）， 其中v0 = wvn = u。 为一有向n-圈。 若V\\V(C)中存在一顶点v，它既是尾在C中的一弧的头，又是头在C中的另一弧的尾：则易见，C中存在相邻的两个顶点vi和vi+1， 使(vi , v)和(v, vi+1 )都是D的弧。于是u在有向(n+1)-圈 (v0，v1，……，vi，v，vi+1，……，vn) 中（其中v0 = vn = u）。 否则，V\\V(C) 可划分为二不相交集S与T，使连接S和C的每一弧的头都在S中；使连接T和C的每一弧的尾都在T中。由D的双向连通性知 S，T，（S，T） 都是非空的。 且D中存在一弧（v，w） v0 使 v S，w T。 vS从而D中存在有向(n+1)-圈 (v0，v，w，v2，……，vn) 其中v0 = vn v1= u。 结论也成立。 # Tv2w 定理10.4 (Ghouila-Houri ,1960) 设D为严格的，且 min{-，+} /2 > 1，则D包含一有向Hamilton 圈。 证明：反证，假设D不包含有向 Hamilton 圈。令 C = （v1，v2，……，vq，v1） D中一最长有向圈。易见，C的长 q > /2（习题10.1.7)。 令P为 D - V(C) 中的一条最长有向路，其长为m，其起、终点分别为u和v。显然， q +m + 1 (1) m < /2 (2) 记 S = { i | (vi-1, u) A} ， T = { j | (v, vj) A} 。 则，首先有 S T = 。 （否则，假设 i S T ，则 Ci，i-1(vi-1，u) P( v, vi ) （Ci，j表示圈C的（vi，vj）-节） 为D 中有向圈，其长为 q+m+1 ，这与C的选择相矛盾。）后面我们将推导出以下 断言 |S T| q - m + 1 ，且S，T 。 (3) 于是，由 S T = 及 S，T 知， 存在 i，k > 0 使 i S， i+k T （ mod q ） i+j S T （ mod q ） 1 j < k 。 (4) 由(3)，(4)可得 k m 。 C 长=q于是，D中存在一有向圈 P 长=mvu Ci+k，i-1 (vi-1 , u) P (v , vi+k) ， 它的长 = q + m + 1 - k q + 1，矛盾。 来证断言：首先注意到，由于P为D - V(C)中的 vi-1vi+k最长有向路，我们有 ND(u)V(P)V(C) ， vivi+148 ∴ dD(u)dP(u)S 。 但 dD(u)/2 , dP(u)m ， ∴ |S| /2 - m 。 (5) 类似地 |T| /2 - m 。 (6) ∴ |S T| = |S| + |T| - 2m (q + m + 1) - 2m (由(1)) = q - m +1 。 再由(2)及(5),(6)得 S，T 。 # 习题 10.3.1. 试用定理10.4推出定理4.3 。 10.3.2. D的有向Euler环游是指遍历D的每一弧恰好一次的有向闭途径。证明：D包含有向Euler +-环游 当且仅当 D是连通的，且对每个顶点有 d(v) = d(v) 。 设有向图D满足： ① d+(x) - d-(x) = m = d-(y) - d+(y) ; ② d+(v) = d-(v) , 对 v V\\{x,y} 。 利用习题10.3.2.证明：D中存在m条弧不重的有向（x，y）-路。 10.3.3.* 证明：包含奇圈的双向连通有向图也包含有向奇圈。 10.3.4. 称非平凡有向图D是k-弧连通的，如果对V的每个非空真子集S，都有 |(S, S)| k 。证明：非平凡有向图是双向连通的当且仅当它是1-弧连通的。 10.3.5. 图G的伴随有向图D(G)是指把G的每边e都用两条相反方向而和e有相同端点的弧代替所得的有向图。证明： (a) G中的路 和D(G)中的有向路 之间存在一一对应 ； (b) D(G)是k-弧连通的当且仅当G是k-边连通的。 工件排序问题 设一机器要加工几种工件J1，J2，……，Jn ；每当加工完一种工件Ji后，为了加工下一工件Jj ，机器必须用tij时间进行调整。 问题 求加工顺序，使总调整时间最短。 在赋权（tij）有向图（V(D) = {J1，J2，……，Jn }，每对顶点间有二反向弧连接）中求一最小权有向Hamilton 路。 （如果生产过程是反复进行，则问题变成求最小权有向Hamilton 圈 。） 注 在赋权有向图中求最小权有向Hamilton 圈（路）问题是NP-hard prob. 。 代替办法 （Heurestic alg. ) 1. 作有向图D, 使V(D) = {v1，……，v}，且 (vi, vj) A(D) tij tji i j 2. 在D中找一有向Hamilton 路P作为工作排序。（有‘好’算法） 49 注。 本算法去掉了矩阵[ tij ] 中较大的那一半，因此‘有理由’期望得到较好的结果。当然，这只是一种一厢情愿的想法而已。例如，右图情况下，“去掉了矩阵[ tij ] 中较大的那一半”后，得到的是右图中用直线段构成的竞赛图，其中的最短Hamilton 有向路的长为12；而最优解为4。 2 2 又，注意到“去掉了矩阵[ tij ] 中较大的那一半”后所得赋 10权图（包含竞赛图）中求该图的最小权Hamilton 有向路问题， 15由前述知，仍然是NP-hard 困难问题。 11公路系统的单行线化 121151510 问题 任给一图G是否有一双向连通定向图？ 10显然，G有一双向连通定向图 G为2-边连通图。 定理10.5 (Robins,1939) G为2-边连通图 G有一双向连通定向图 。 证明：由G为2-边连通知，G中含一圈G1 。归纳地定义G1，G2，……如下：若Gi不是G的生成子图，任取G不在Gi中的一个顶点vi 。由习题3.2.1.，易见，存在 vi 到Gi 的两条边不重的路Pi和Qi 。定义 Gi+1 = Gi Pi Qi 。 由于(Gi+1) > (Gi) ，该序列一定终止于G的一生成子图Gn上。 今对Gn定向如下：把G1定向为一有向圈； 把Pi定向为一以vi为起点的有向路；把Qi 定向为以vi为终点的有向路。显然，每个Gi有一双向连通定向。由于Gn是G的一生成子图，G也存在双向连通定向图。 定理（Nash-Williams ，1960） G为2k-边连通的 G有k-弧连通定向图。 （证略） （即 |（S，S ）| k S V） 上述定理的特殊情形为以下定理， 其证明较容易，留给读者来完成： 定理10.6 G为2k-边连通，且有一Euler 迹 G有一k-弧连通定向图。 习题 10.5.1 通过考察Petersen图证明以下结论不成立：每个图都有一定向图，使得对每个S V，（S，S ）和（S，S）的弧数相差最多为1。 10.5.2. (a) 证明Nash-Williams定理下述命题： 若G的每个键至少有2k-条边，则存在G的一个定向图，其中每个键在每个方向上都至少有k-条弧。 (b) 通过考察Grotzsch图证明以下结论不成立：若G的每个圈至少有2k-条边，则存在G的一个定向图，其中每个圈在每个方向上都至少有k-条弧。 50 网络 流 一个网络（Network）N是由一有向图（称为基础有向图（underlying digraph）；二特定的不相交顶点子集X和Y；以及弧集A上定义的非负整数值函数c()（称为容量函数） 组成的。其中，X的每个顶点称为发点（source）；Y的每个顶点称为收点（sink）；I = V \\ (X Y)中每个顶点称为中间顶点（intermediate vertex）；每弧a上c(a)的值称为a的容量（capacity）。 设f(.)为定义在弧集A上的实函数，对任一弧子集K，记 x11v42x263 41 53v151v23y1 22y2y3 f(K)f(a) 。 aKv34当K=（S，S ）时，记 f+(S) = f(S,S) 。 类似地，记 - f(S) = f(S, S) 。 由此，特别地，有 f+(v) = ( {v}, V\\{v} ) ； f -(v) = ( V\\{v), {v} ) 。 定义在A(D)上的整数值函数f(·)若满足以下条件，就称为网络N上的流（flow）： ① 0 f(a) c(a) ， a A(D) 。 称为容量约束（capacity constraint）。 ② f+(v) = f -(v) v I 。 称为守恒条件（conservation condition）。 注 f(a)可当作物资沿弧a输送的流量。但不能将流当作水的流动！ 零流（zero flow）f f(a) = 0 ， a A(D)。 设f是网络N上的流，而S是其顶点子集。称 +- f(S) - f(S) 为流出S的合成流（resultant flow out of S） -+ f(S) - f(S) 为流进S的合成流（resultant flow into S） 容易证明（习题）， f(S) - f(S) = + -+ - (fvS- (v)f(v)) + f(X) - f(X) = f(Y) - f(Y) （记为） = valf 称为流f的值 。 最大流（maximum flow）f 不存在流f＇使val f＇ > valf 。 求解最大流问题时，为简化计，可将多收、发点问题转化为单收、发点问题 ，如右图所示：往N中加两顶点x和y作为新网络N＇的发点和收点；并用容量为∞的一条新弧将x连接到X中每个顶点； 用容量为∞的一条 ∞新弧将Y中每个顶点连接到y。 xN和N＇中的流f和f＇之间有一简单的对应关系： ∞当f满足条件 +- f(xi) - f(xi) 0 xi X ； ∞-+ f(yj) - f(yj) 0 yj Y ； （不难证明，对求解最大流问题只要考虑这种情形就够 N∞XY∞∞ 51 y 了。）可定义f＇如下 易见，f＇确实是N＇上的流，且 valf＇= valf （习题） 反之，N＇的任一流f＇在N的弧集上的（restriction）f是N上的流，且 valf = valf＇（习题）。 由上述知网络N和N＇有相同的最大流的值，为简单计以下三节中将只讨论单收、发点之情形。 f(a)f(a)f(xi)f(xi)f(y)f(y)jjaA(D)a(x,xi) a(yj,y) 习题 11.1.1. 对于下列各网络，确定所有可能的流和最大流的值： 11.1.2. 证明：对N中任一流f及任一S V，都有 113333x2 4 2yx2 4 2y33331 1 (f(v)f(v)) = f+ (S) - f- (S) 。 vS11.1.3. 证明：对N中任一流f 有 f+(X) - f-(X) = f-(Y) - f+ (Y) 。 割 设网络N只有一个收点x及一个发点y， S V(D) 。称 （S，S ）为N中的 割（cut） x S， y S 。 称 cap K = c(a) aK为割 K = （S，S ）的容量。 引理11.1 对N中任一流f及任一割（S，S ） 有 valf = f+（S）- f-（S）。 证明：注意到 f(v)f(v)valfvx ， 因此有0vS\\{x} valf = (f(v)f(v)) = f+(S) - f-(S) 。 # vS 称弧a为： f-零的 f(a) = 0 ； f-正的 f(a) > 0 ； f-不饱和的 f(a) < c(a) ； 52 f-饱和的 f(a) = c(a) 。 定理11.1 对N中任一流f及任一割K =（S，S ）有 valf cap K ； 又，上式中等号成立 （S，S）中每弧为f-饱和的， 且 （S，S）中每弧为f-零的 。 证明：由容量约束知 + f(S) cap K (1) - f(S) 0 (2) 再由引理11.1知定理的第一个结论成立。又， (1)中等号成立 （S，S）中每弧为f-饱和的 ； (2)中等号成立 （S，S）中每弧为f-零的 ； 从而定理的第二个结论也成立。 # 最小割（minimum cut）K 不存在割K 使 cap K < capK 。 显然，若 f 为最大流，K为 最小割，则 valf capK 。 推论11.1 设 流f 及 割K 使 valf = cap K ， 则f为最大流，K为最小割。 习题 11.2.1. 在右图所示的网络中：求所有的割；求最小割的容量；并证明由粗体字所指出的流是最大流。 11.2.2. 证明：若N中不存在有向(x,y)-路，则其最大流的值及最小割的容量都是零。 11.2.3. 若( S,S )和( T,T )都是N中 * * ~~~~22x342213 330125 y的最小割，证明：( S T,ST ) 和 (ST,ST)也都是N中的最小割。 最大流最小割定理 设f为网络N中的流，P为N中一条路，令 c(a)f(a)f(a)(P) = min(a) 。 (a)a为P的顺向弧a为P的反向弧 ； aA(P)称路P为 f-饱和的 (P) = 0 ; f-不饱和的 (P) > 0 ; f-可增路（f-incrementing path）P P是以发点x为起点，以收点y为终点的 f-不饱和路 。 若N中有一f-可增路P，则，易见，f不是最大流。这时，可沿P输送一附加流 而得一新流 f′： 53 f(a)(P)f(a)f(a)(P)f(a)a为P的顺向弧a为P的反向弧 。 (11.9) 其它 这时， valf′= valf + (P) ， 并称 f′为基于P的修改流（revised flow based on P）。 定理11.2 N中的流f为最大流 N不含f-可增路 。 证明： ： 反证，若N中含一f-可增路P，则f不是最大流，因为基于P的修改流 f′的值更大。 ： 令 S = { v | f-不饱和（x，v）-路} ， 则显然有 x S ； y S ； ∴ K = （S，S ） 为割。 注意到，这时（S，S ） 的任一弧 a = （u，v）一定是f-饱和的。否则，由于存在f-不饱和（x，u）-路Q， Q可通过a延伸为f-不饱和（x，v）-路，从而 v S，矛盾。 类似地，（S，S）中任一弧 一定是f-零的。 因此，由定理11.1知，valf = cap K 。从而由推论11.1知，f为最大流。 # 定理11.3 (max-flow min-cut theorem , Ford & Fulkerson ,1956) 在任一网络中，最大流的值 = 最小割的容量。 上定理是图论的一重大结果，其它图论结果，例如，偶图的匹配、Menger定理等，可由它利用适当选取网络来导出。 求最大流的算法 原理 ： 1° 以一已知流f（例如，零流）作为开始。 2° 系统搜索f-可增路P。若P不存在，停止（f-为最大流）。 3° 若P存在，求出基于P的修改流f′，令 f f′，并转到2°。 系统搜索f-可增路P标号法 （通过标号‘生长’f-不饱和树T） 开始，标x以l(x) = 。 （此后，在T的生长过程中，T中每个顶点 将标 以 l(v) = (Pv) ，其中Pv是T中惟一的(x, v)- 路。） (1) 若 a = （u，v）为f-不饱和弧，且u已标号， 而v未曾，则标v以 l(v) = min{ l(u), c (a) - f (a) } 。 (2) 若 a = （v，u）为f-正的，且u已标号，而v未曾，则标v以 l(v) = min{ l(u), f(a) } 上述标号过程一直进行到：或者y已标号（“breakthrough”，找到了f-可增路）；或者所有已标号顶点都已扫描，但无顶点可再标号（f为最大流）。 标号程序 （labelling method，Ford & Fulkerson ,1957) 以已给流f（例如，零流）作为开始。 ① 标x以 l(x) = ∞。扫描 （scan） x 。 ② 对正在扫描的（已标号）顶点u， (i) 检查每条以u为尾的弧 a = （u，v）。如果 a 为f-不饱和的，且顶点 v未标号，则标v以 l(v) = min{ l(u), c (a) - f (a) } 。 (ii) 检查每条以u为头的弧 a = （v，u）。如果 a 为f-正的，且顶点v未 标号，则标v以 l(v) = min{ l(u), f(a) } 。 ③ 若y已标号（‘break through’，找到了一条f-可增路），则转到④ ；否则选一未曾扫描的已标号顶点进行扫描，并回到②。如果已标号顶点都已扫描过，停止（得最大流。且由已标号顶点集S，得最小割（S，S） ）。 ④ 找一f-可增路P，令 去掉全部标号，并回到① 。 注 上述算法还不是‘好’算法，例如右图中的 u网络，其最大流的值为2m。但若标号程序以零流开始， 且反复地选取xuvy及xvuy为 f-可增路，则总共要mm进行2m+1次标号程序，因此其计算量为输入长（= xO(log2m) )的指数函数。 1yEdmonds & Karp (1970) 证明，若在上述标号程序 m中采用first labelled first scan （即广度优先）法则， m则，可使该算法成为好算法（复杂性为O(2 ) ) 。 v 习题 11.3.1. 证明：由(11.9)式给出的函数f是valf′= valf + (P) 的流。 11.3.2. 试求右图所示网络的最大流。（答：x1y1184最大流的值=39） 7211.3.3. 证明：在具有整数容量的任一网络v2v1N中，总存在一最大流f，使f(a)在每一弧a上都5197取整数值。 713 22311.3.4. 考察在每条弧a上都伴随一整数 b(a) y22416 c(a)的网络N，试修改标号法，来求N中满足 81224条件 b(a) f(a) c(a) , a A , 的最大 2vv315流f。 （假设存在满足这个条件的初始流）。 411.3.5. 设网络N的每个中间顶点v都伴随x2y3一非负整数m(v)。试修改该网络，并将标号法应 -用于它，来求出满足条件 f(v) m(v) , v V \\ {x,y}， 的最大流f。 11.3.6 试用网络理论证明Hall定理（第五章）。 f(a)l(y)~f(a)f(a)l(y)f(a)~ f f ， 当a为P上的顺向弧当a为P上的逆向弧 其它Menger 定理 引理11.4 设网络N的发点为x，收点为y，且每弧的容量都为1，则 (a) N中最大流的值 = N中弧不重的有向(x,y)-路的最大数目m。 (b) N中最小割的容量 = 破坏N中所有有向(x,y)-路所需去掉的最少弧数n。 证明：(a) 令f*为N中在每弧上取整数值的最大流；D* 为由D中去掉所有f*-零弧而得到的有向（生成子）图。显然， f*(a) = 1 a A(D* ) 。 因此，有 ① dD*(x)dD*(x)valf*dD*(y)d*(y) ； D② dD*(v)dD*(v) v V \\ {x，y} ； 于是，由习题10.3.3.知，D*中，因而D中，有valf * 条弧不重的有向（x，y）-路。因此 m valf * 。 另一方面，设P1，……，Pm为N中任一组m条弧不重的有向（x，y）-路，定义函数 55 1f(a) = 0aA(Pi）其它i1m 显然，f为N中值为m的流。由于f* 为最大流，得 valf* m ， 从而 valf* = m 。 (b) 令 K = (S,S )为N中的最小割，则易见N - K 中从x不可达y。即 K 就是去掉它就破坏所有有向(x,y)-路的弧集，因此 n |K| = capK 。 另一方面，设Z为n条弧的集合，去掉Z后就破坏所有有向（x,y)-路。令S为N - Z中x可达的顶点集。显然，x S， y S ，从而 K = (S,S )为N中的一个割。又，由S的定义知，N-Z中不含 (S,S )的弧，因此 K Z，从而 capK capK = |K| |Z| = n ， ~~~~~~ ∴ n = capK 。 # 定理11.4 设x和y为有向图D中任二顶点，则 D中弧不重的有向(x,y)-路的最大数目 = 破坏D中所有有向(x,y)-路所需去掉的最少弧数。 证明：由D作网络N：其发点为x，收点为y，每弧容量1。再用引理11.4及 定理11.3即得。 # 定理11.5 设x和y为图G中任二顶点，则 G中边不重的(x,y)-路的最大数目 = 破坏G中所有(x,y)-路所需去掉的最少边数。 证明：作图G的伴随有向图（associated digraph），再用定理11.4即得。 # 推论11.5 (Menger 定理） G为k-边连通的 G中任二顶点都至少被k条边不重的路所连接。 证明：由k-边连通定义即得。 # 定理11.6 设x和y为有向图D中二不同顶点，且D中没有连x到y的弧，则 D中内部不相交的有向(x,y)-路的最大数目 = 破坏D中所有有向(x,y)-路所需去掉的最少顶点数。 证明：由D作有向图D’ 如下： ① 将每个 v V \\ {x., y} 分成二新顶点v’ 及v’’ ，并连以新弧(v’,v’’)； ② 将D中以 v V \\ {x., y} 头的弧代之以以 v’ 为头的弧；以v为尾的弧代之以以 v’’ 为尾的弧。 于是易见，D’ 中一有向(x,y)-路与D中一有向(x,y)-路之间存在1-1对应关系（通过将D’中一有向(x,y)-路上的每一(v’, v’’ )弧收缩成v；或将D中一有向(x,y)-路的每一顶点v成弧(v’, v’’ )）。 又，易见， D’ 中二有向(x,y)-路为弧不重的 对应的D中的二有向(x,y)-路为内部不 相交的。 因此， D’ 中弧不重的有向(x,y)-路的最大数目 = D中内部不相交的有向(x,y)-路的最大数目。 类似地，破坏 D’中所有有向(x,y)-路所需去掉的最少弧数。 = 破坏D中所有有向(x,y)-路所需去掉的最少顶点数。（习题11.4.1.) 再用定理11.4，定理得证。 # 定理11.7 设x和y为图G中二不相邻顶点，则 G中内部不相交的(x,y)-路的最大数目 = 破坏G中所有(x,y)-路所需去掉的最少顶点数。 56 ~ 证明：将定理11.6用于G的伴随有向图上即得。 # 推论11.7 （Menger 定理）设 (G) k + 1，则 G为k-连通的 G中任二不相同顶点至少被k条内部不相交的路 所连接。 证明： 显然。 # 习题 11.4.1. 证明在定理11.6的证明中提到的命题：破坏 D’中所有有向(x,y)-路所需去掉的最少弧数 = 破坏D中所有有向(x,y)-路所需去掉的最少顶点数。 11.4.2. 从定理11.7导出Konig 定理。 11.4.3. 设S和T是图G中二 不相交顶点子集。证明：起点在S、终点在T的 顶点不相交的路的最大数目 = 把S和T分离开来所需去掉的最少顶点数。（即，去掉后没有一个分支同时包含S和T中的顶点） 11.4.4.* 证明：若G为k（ 2 ）-连通图，则G的任何k个顶点共圈。 可行流 在网络N的每个发点xi 上指定一非负整数(xi)，称为供给（supply）；在每个收点yj上指定一非负整数(yj)，称为需求（demand）。称N中的流 f为可行流（feasible flow） f+(xi) - f -(xi) (xi) xi X； f -(yj) - f+(yj) (yj) yj Y。 问题 存在可行流的充要条件是什麽？ 记 (S) = (v) ； vS (S)(v) 。 vS 定理11.8 (Gale,1957) N中存在可行流 c(S, S ) (Y S) - (X S) S V。 证明：由N作N’ 如下： ① 往N里添加二新顶点x及y； ② 从x到每个xi X 连以容量为(xi) 的弧； ③ 从每个 yj Y到y 连以容量为 (yj) 的弧； ④ 将x和y分别当作N’ 的发点和收点 。 易见，N中有可行流 N’有一个流使割(Y, {y})中每一弧都饱和。 （习题11.5.1.) 但N’中对应流的值 = (Y) = cap(Y,{y}) 。由推论11.1知， 它是N’中的最大流，故 N中有可行流 对N’ 中每一割(S{x}，S {y})都有 57 但 cap(S {x}，S {y}） (Y) 。 cap(S {x}，S {y}） = c’(S,S) + c’(S,{y}) + c’({x},S ) (c’(.)表示N’中的容量函数） = c(S,S) + (Y S ) + (X S ) ， 而 (Y) = (Y S ) + (Y S ) ，得证。 # 58 因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- oldu.cn 版权所有 浙ICP备2024123271号-1
违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务