图论及其应用

图和子图 图

图 G = (V, E)， 其中 V = {v1,v2,......,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)?V(G),?(G)?E(G).。

习题

1.1.1 若G为简单图，则

a p q b c r d e f G = (V, E)

??????? 。

?2?1.1.2 n ( ? 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。

同构

在下图中， 图G恒等于图H , 记为 G = H ? V（G)=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}个。证明：

?n?k??k?1? (a). ?(Tm,n) = ???(m?1)?? 其中 k =[n/m] .

?2??2? (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中两个顶点相邻当且

2

仅当它们在G不相邻。

(a). 画出Kcn和 Kcm,n。

(b). 如果G ? G c则称简单图G为自补的。证明：若G是自补的，则 ? ? 0, 1 (mod 4)

关联矩阵M(G)与邻接矩阵A(G)

M(G)=[mi,j]???, A(G)=[ai,j]??? ,

其中 mi,j = 顶点vi与边ej 的关联次数= 0, 1, 2. ai,j = 连接顶点vi 与 vj 的边数 。 例。

e1?1?1M(G)???0??0

e21100e30110e40011e51001e60002e71?v10?v2?1?v3?0?v4v1e5e6v4e1e2e7e4G = (V, E)v2e3v3v1?0?2A(G)???1??1

v22010v31101v4101?v1?v ?2?v3?1?v4

子图

子图(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?中所有边的端点为顶点集的的子图。 例。

G[{f, c]}G[{c, d, e}]

3

u

ea yfv

dghb以上两种子图，其实，xcw对应于取子图的两种基本运算。下面是取子图的另两种G=(V, E)G[{u,w,x,y}]G[{u,w,x}]基本运算：

G - V’ ? 去掉V?及与V?相关联的一切边所得的剩

余子图。

? 即 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仍可能为相交的）。 并图 G1?G2 , 当不相交时可简记为 G1+G2. 交图 G1?G2 .

习题

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? .

v?V系1.1 任一 图中，度为奇数顶点的个数为偶数。

例。任一多面体中，边数为奇数的外表面的数目为偶数。 证明。作一图，使其顶点对应于多面体的面，并使其中二顶点相邻当且仅当对应的两个面相邻。...... ?

4

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的度序列。证明：非负整数序列 ( d1 ,d 2, ......, d n) 为某一图的度序列 ?

3-正则图?di?1ni是偶数。

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 。 u终点（terminus） x。 ea内部顶点（internal vertex） y, v, w, x。

fy （注意，中间出现的x也叫内部顶点。）

g长 ? 边数（重复计算）。

dh节（段，section）。 例如W的(y, w)-节=yvw 。

-1

W（逆途径）, WW’（两条途径W与W?相衔接）。 迹( trail) ? 边各不相同的途径。 例如，yvwyx 。 xc路 (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。

vbw

5

记号 对任一非 S?V ，令 S = V\\S, 记（称为边割）

[S, S] = G中 一 端在S中，另一 端在S中 的一切边的集合。 例。（命题）G连通 ? 对任 S ? V 都有 [S, S] ? ? 例。（命题） 简单图G中， ? ? k ? G中有 长 ? k 的路。

习题

k

1.6.1 证明：G中长k为的(vi ,vj )-途径的数目,就是A中的(I, j)元素。 1.6.2 证明：对简单图G有， ???对于? > 1，试给出??????1?? ? G连通。 ?2????1??的不连通简单图。 ?2?1.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 = { x?V ? d(u, x) = 偶数 }, Y = { y?V ? 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的

6

最后一个公共顶点； 而 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 ? 含二条边不重的圈。

习题

1.7.1 若边e在G的一闭迹中，则e在G的一圈中。 1.7.2 证明：(a). ? ? ? ? G含圈。

(b)*. ? ? ? + 4 ? G含两个边不重的圈。

最短路问题

赋权图（weighted g.)(权 ? 1 之推广 ) 权( weight ) w(e) ? 0. w(H) =

w(e), H ? G .

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 ? ?Sk?1?} = 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 ? Sk?1? , u ? S k-1 } = min { l( v ) ? v ? Sk?1}

其中， 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 } 。

7

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 }。

(3). 若 k = ? - 1 , 仃止；不然，令 k ? k+1 ,并回到 (2) 。

S k-1u ju ku 0S kv?S 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 复杂性

3n .001sec .008sec .027sec .064sec .125sec 5n .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). 一图的围长（即最短圈的长）。 并说明你的算法好到什么程度。

8

树 树

无圈图（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). 以下结论不一 定成立： ? 闭途径 ? ? 圈 。

定理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)?2??2??2 ，

v?V由此知推论成立。

例。（命题）恰只包含二度为一顶点的树是路。

习题

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 ? )是一 棵树的度序列，当且仅当

?di?1?i?2(??1)。

9

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为树。 证明：注意到以下事实即可，

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 。

10

键（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的补图，记为： ?H(G) 。

特别地，当T为G的生成树时，称 ?T 为G的余树。

定理2.6 设T为连通图G的一个生成树， e为T的一条边，则

GT?T(1).余树?T 不包含G的键；

(2). ?T + e中唯一包含的G的一个键。 证明：(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为二集合，记其对称差( 即（S1?S2）-（S1?S2） )为 S1 ? S2

称为它们的环和(ring sum)。 性质

1) 图G的每一边割是G的一些割集的边不重并。

2) 设B1 ,B2 为图的任二边割，则B1 ? B2 也是G的边割。 （对任二非空V1 ,V2 ? V， 有

11

3) 4) 5) 6) 7) 8)

习题

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， F?H 是H的生成树； (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) B1?B2 是G的键的边不重并集； (b) C1?C2是G的圈的边不重并集；

(c) 对G的任一边e，(B1?B2)\\{e}都包含键； (d) 对G的任一边e，(C1?C2)\\{e}都包含圈。

2.2.9 证明：若图G包含k棵边不重的生成树，则对于顶点集每一划分(V1 ,V2 ,...,Vn )，端点在这个划分的不同部分的边的数目至少为 k(n-1)。

[V1 ,V1]?[V,V] = [V2 , V2], 其中V3 =(V1 ?V2)?(?V1? ?V2 ) ）。 设边子集E?与E”分别为G中一些圈的边不重并，则E??E” 亦然。 G的每个圈可唯一地表为G的一些基本圈的环和。 G的每个边割可唯一地表为G的一些基本割集的环和。 边子集E?为G中一些边不重圈的并集

? 边子集E?与G中每个边割有偶数条公共边。 边子集B为G的一个边割

? 边子集B与G的每个圈有偶数条公共边。

G为一些圈的边不重并 ? d(v) = 偶数 ? v ? V

割点

称顶点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中

12

?? 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)的逆命题不成立。

2.3.2 证明：恰有二顶点为非割点的简单连通图必是一条路。 2.3.3 在简单连通图G中证明：

v为G的割点 ? G的任一生成树不以v为叶。

生成树的计数及Caley公式

本节只讨论无环连通图。

将图G的关联A??? 矩阵中每列的两个1元素之一改为 -1，得一新矩阵，记为Aa（它是G的一个定向图的关联矩阵）。例如：

e1v1?1?Aa?v2?0v3?0?v4??1 e21?100e301?10e4001?1e50?1? ?0???1?v1e1e2e5v2e3记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 ]m?n ， Q=[ qij ]n?m ，且m ? n 则

13

det(PQ)?1?j1?...?jm?n?pij1...pmj1.........p1jmpmjmqj11qjm1.........qj1m... qjmm

...?...

T

引理2 连通图的生成树数目 = det（AA）。 证明：由Binet-Cauchy定理知，

T2

det(AA) = ∑(detA1) (对A的所有 v-1阶子方阵A1求和） 但由引理1知

?detA1? = ??10A1的列对应于G的一生成树其它

得证。 ?

无环图G的度矩阵

K = [ kij ]? ? ? ， 其中

???kij??ij?d(vi)v1?2?K???1?0???1当i?j且vi与vj间有?ij条平行边

当i?j

例如对本节开头的例子有

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)-元素的代数余子式

v4v2?13?1?1v30?12?1v4?1?v1?1?v2 ??1?v3?3?v42

=(?1)2?30?1?1?1?1?1 = 8 。 3?1

n-2

定理（Cayley） K n 中共有 n个不同的生成树。 证明：用上述定理可直接证出（习题）。 ?

习题

2.4.1 求Ｋ３，３的生成树数目。

n-3

2.4.2 若ｅ是Ｋｎ的一条边， 则 Ｋｎ－ｅ的生成树数目为 (n-2)n 。

连线问题

问题 设城市vi与vj间建立直接通信线路的费用为cij（ ? 0）。

14

建设连接 {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 也是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 v??V? 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

15

若迹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 。

假设Wn 不是Euler环游 ，令

S = { v ? dGn (v ) > 0 } ， ?S = V\\S 。 易见，

S ? ? ； vn ??S 。

令 vm 为Wn 在S中的最后一个顶点，则，显然，

?S,S?Gm??em?1? 。

dGn(v) = 偶数， ? v ? V 。

因此Gn 中无割边，特别地，Gn中与vm相关联的任一边e是Gn中的非割边，因而也是Gm中的非割边。但 em?1 ? e (∵em?1 ?Gn )，于是在Gm 中，割边em?1 与非割边e都和vm 相关联，而迹Wn却取的是割边em?1，这与算法之 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）。

21

又，

Hamilton 圈

Hamilton路 ? 生成路（spanning path ） Hamilton 圈 ? 生成圈

Hamilton 图 ? 包含Hamilton 圈的图

定理4.2 G为Hamilton 图

? ?(G-S) ? ? S ? ? S ? V

证明：令C为G的一个Hamilton 圈 ,则对任一 S ? V 必有

非Hamilton 图 ?(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? ? S?T ， ??S?T ? < ? 。 又， S?T = ? 。

(不然，假设存在vk ? S?T ，则G中有Hamilton 圈 v1 v2 。。。vk v? v???。。。vk+1 v1 ， 矛盾） ∴ d(u) + d(v) = ? S ? +? T ? =? S?T ? < ? 这与? ? ?/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) ? ? 。

22

但H ? G?? ， ∴ dG??(u) + dG??(v) ? dH(u) + dH(v) ? ? 。 而 uv ? E(G??), 这与G??之定义矛盾。

同理，每个fj ? E(G?) 。故 G? = G?? 。 ? 定理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。

??14.3.4. 若? ? 3的简单图G中，??C2?1 ，则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 图

旅行售货员问题(travelling salesman prob.)

问题 在赋权完全图中找最小权Hamilton 圈（最优圈） 。 （NP-hard prob。） （问题 任给一图G， G是否为Hamilton 图 ？ （NP-complete prob。）） 代替办法 找一reasonably good solution。例如，先找一Hamilton 圈 C=v1v2 ...v? v1 ，再加以改进： 对任i与j, 1

Cij＝ v1v2 ...vivJ vj-!...vi+1vj+1vj+2 ...v? v1 。 若对某i与j有

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相关联的边中权之和为最小的二边。

23

习题

*

4.4.1 设赋权完全图G的权满足三角不等式，即对任x,y,z ? V 都有 w(xy) + w(yz) ? w(xz) 。

证明：G中最优圈的权最多是2w(T), 其中T是G中的一最优树。

匹配 匹配

匹配（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? = M?E(P) 也是G的匹配， 且? M?? = ? M? +1，这与M 为最大匹配相矛盾。

? ：反证，假设M不是最大匹配，取G中任一最大匹配M*。。令 H = G[ M?M*] 。

显然， 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 = H1?H2???? Hn ，则称G为k-可因子分解的 。

(a) 证明：① Kn,n与 K2n是1-可因子分解的； ② Peterson图不是1-可因子分解的。 (b) 下面的图中哪些有2-因子：

24

(c) 用Dirac定理若G是简单图，? 是偶数，且? ? 1+?/2 ，则G有3-因子。 5.1.6* 证明：K2n+1可表为n个连通的2-因子的并。

5.1.7 证明：任连通偶图G = （X,Y, E）的2-划分（X，Y）是唯一的。

偶图的匹配和覆盖

邻集（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 = Z?X ， T = Z?Y 。

**

显然， S\\U 与T 的顶点在M 下相匹配（注意到：任一M-边若有一端点在Z中，则其另一端一定也在Z中）。因此，

?T? = ?S? - 1 ； N(S)? T 。 但 N(S)? T ， 故 N(S) = T ，从而

?N(S)? = ?T? =?S?- 1

推论 5.2 (marriage theorem) 若G 为 k-正则偶图（k>0 )，则G有完美匹配。 证明：设G的2-划分为(X, Y)，则 k?X?=?E?=k?Y? ， ? ?X? = ?Y? 。

又，对任S ? X，令E1和E2 分别为与S和N(S)相关联的边集。易见，

E1 ? E2 。

∴ k?S? = ?E1? ? ?E2? = k?N(S)?

∴ ?S? ? ?N(S)? ? S ? X 。

故G中有使X中每个顶点都饱和的匹配M，它也是完美匹配。 ?

称 K（? V）为G的一个覆盖（covering）

? G中每边至少有一端在K中。

最小覆盖（minimum covering）K 。

对G中任一覆盖K及任一匹配M ，显然，恒有 ?M? ? ?K?。 特别地，有

25

~

?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 = Z?X， T = Z?Y 。

**

与定理5.2之证明类似，我们有： T中每顶点都是M-饱和的；T与S\\U中顶点在M下相匹配；N(S) = T。 记

~定理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 证明：一个5?5方格棋盘去掉其对角上的两个1?1方格之后，不可能用1?2长方格恰好添满。

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 （当i?j）。证明：（A1 ，A2 ，??，An）有一个相异代表系 当且仅当

?

?A?? ?J? ? J ? {1,2,...,n} 。

ii?J 5.2.5 矩阵的一行或一列统称一条线。证明：一（0,1)-矩阵中 ，含所有1元素的线的最小条数 = 两两都不在相同线上的1元素的最大个数。

5.2.6 (a) 证明：Hall定理的一个推广：偶图G =（X,Y; E) 的最大匹配的边数是 ?X? - max{ ?S?-?N(S)? } 。

S?X (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都是非负实数，且

?ci?1ki?1 。

5.2.9 若偶图G=(X,Y,E)中，X中每顶点的度?Y中每顶点的度，则G有使X每顶点都饱和的匹配。

*

5.2.10 设偶图G=(X,Y,E)中，Y?为匹配M在Y中的端点集，则存在G的最大匹配M，其端点集包含Y?。

26

完美匹配

称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? 。

*

? ： 反证。假设存在图G 满足条件（*），但不含完美匹配。令G 为G的不含完美匹配的极大生

*

成母图。由于G-S是G-S的生成子图，

*

o(G-S) ? o(G-S) ? ?S? ? S ? V 。 ***

即G满足条件（*），又，上式中令S=?得o(G)=0，因此 ?(G)=偶数。 令

U?{v?V(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) ， 而 xz?E(G)

**

又，因 y ? U，一定存在 w ?V(G-U) 使 yw ? E(G)。 令

**

M1 与 M2 分别为 G+xz 与 G+yw中的完美匹配。

*

考虑 G+{xz，yw} 中 M1?M2 的边导出子图 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,1891) 每一不含割边的3-正则图都有一完美匹配。

证明：对任S ? V，令 G1 ，??，Gn 为G-S中的所有奇分支。记mi 为一端在Gi中而另一端在S中的边数。则

mi?v?V(Gi)?d(v)?2?(G)?3?(G)?2?(G)?奇数。

iii但G中无割边，因此mi ? 3。从而

3?S?=

?d(v)??mv?Si?1ni?3n 。

∴ ?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 。

27

*

5.3.4 证明Tutte定理的推广： G的最大匹配的边数 = (? -d)/2 ，其中 d?max{o(G?S)?S} （C.Berge)

S?V

人员分派问题

问题 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， S?{u}，T?? 。

② 若N(S)?T,转到③；否则，N(S)=T,停止（无完美匹配）。 ③ 取 y ? N(S)\\T 。若y为M-饱和的，设 yz ? M ，则 S?S?{z} ， T?T?{y} ， 回到②；否则，存在M-可扩路P。 M?M?E(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{y?Y例。 下面是一可行顶点标号： ?l(y)?0?记

x?Xy?Y

El?xy?El(x)?l(y)?w(xy)??

Gl (相等子图，equality subgraph）

? 以El为边集的G的生成子图。

**定理5.5 设偶图G的可行顶点标号l使Gl 包含一完美匹配M，则M是G的最优匹配。 证明：显然，M也是G的完美匹配，且

*w(M*)?e?M*?w(e)??l(v) 。

v?V但对G的任一完美匹配M有

28

*w(M)?因此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。计算

e?M*?w(e)??l(v) 。

v?V~

l(x)?l(y)?w(xy)} ?l = min{x?S~y?T及f.v.l. l ：

v?S?l(v)??l~? l??l(v)??lv?T

?l(v)其它?~ l? l ， Gl ? G~ 。 l

③ 选取 y?NGl(S)\\T，若y为M-饱和的，则存在 yx?M ， 作

S??S?{x}， T?T?{y}，

并转到② ；否则，令P为Gl中的M-可扩-(u,y)路， M?M?E(P) ， 并转到① 。

2

注1 算法中每计算一次新的Gl的计算量为O(?)；在找到M-可扩路之前，至多进行 ?X?次 搜索（每次可能作一次新的Gl的计算）；而初始匹配M至多扩大?X?次。因此是个‘好’算法（计算复

4

杂性为O(?) )

注2 本算法也可用于解人员分派问题。

习题

5.5.1 所谓n×n矩阵的一条对角线是指它的任n个两两不同行、不同列元素的集合。对角线的权是指它的n个元素的和。试找出下列矩阵的最小权对角线：

?4?7??8??6??4565658512137107910911?4??6? （答：权=30） ?7?8??

29

边着色 边色数

前提 本章只讨论无环图。

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个人举行一些两两会谈，每次会谈用一个单元时间。问最少要多少单元时间，才能安排完所有会谈？

例。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) 。

v?Vv?VC为最优k-边着色（optimal k-edge colouring） ? C不能再改进 。

30

引理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) ? v?u ?

?c'(v)??c(v) 这与C为最优矛盾。

v?Vv?V?

定理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各表示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,1964) 对简单图G有 ?? = ? 或 ? + 1 。 证明：（Bollobas）不妨设G中 除uv1外 都已用色 1,2,??,? +1

进行了正常边着色。注意到，G的每个顶点上都至少有一色未表现。令u，v1 各有色i0，i1 未表现。我们可逐步找到不同的色、边序列：

i0 ， i1 ， i2 ，??，ij ，?? ； uv1 ，uv2 ，??，uvj ，?? 。 其中， 色ij 是顶点 vj 上未表现的（任意取定的）一色；

31

边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] 的每个分支是路或圈，由

i0?ik色i0与ik的边交错组成，且

u，vk+1，vl 在H中的度? 1。

从而，该三顶点不可能同时在H的一分支中。这时只有二可能情形： ① 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) 。

32

(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?）

1?i?p节课，所需教室数c ? ?? 。

问题 能否适当排课，使全部l节课在p（? ? ）节内排完，且每节课所用 教室数? ?? ？（∴???Ei??? ? 1? i ? p ）

引理6.3 设M，N为G的二不相交匹配，且?M?>?N?，则存在G的二不相交匹配M?，N?使?M?? =?M?-1 ，?N?? = ?N?+1 ，且M??N? = M?N 。

证明：令H = G[M?N]，则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为简单偶图，且学生不提出要求的情况下，也是如此。

?l??p??l??p??l??p??l??p?????p?????p? 33

独立集和团 独立集

定理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| = ? - ? 。 ∴ ????? 。 #

注 由上述证明知 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 。

34

? 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 的各分支的顶点集。称 Gi = G[Vi?S]

为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定理之证明）。下面是这方面的一些结果：

35

例。设图G 中度序列满足：d1 ? ??? d? ，则 ? ? maxmin{di?1,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 。 因此，首先有

?(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{di?1,i} 。

i

8.1.4. 利用习题8.1.3 证明：

(a) ? ?

(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(。 (b) 试证：不存在恰有k+1个顶点的k-临界图。

8.1.11. (a) ?(G1?G2) = ?(G1) +?(G2) ，其中G1?G2 称为图G1与G2的联图，它是将

36

?2?? 。

它们间的每对顶点都用新边连起来所得的图。 (b) G1?G2是临界图，当且仅当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 。

在上述两种情况下，我们都有 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 也满足要求；一般，设

37

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-临界图。

?k??8.3.2(a) 设G是围长至少为6的k-色图（k ? 2）。作一新图H如下：取k?个新顶点集S及G的??

???*

个互不相交的拷贝，且建立G的拷贝与S的?个顶点的一一对应。再将G的每个拷贝与它在S中相对应的?个顶点之间用一匹配连接起来。证明：H的色数至少为k+1，其围长至少6。

(b) 试证：对任k ? 2，都存在围长为6的k-色图。

平面图 平图和平面图

图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为非平面图。

38

证明：类似，略。

平面嵌入的慨念可推广到其它平面上。称 图G可嵌入于曲面S上 ? G可画在S上，使它的边仅在端点处才可能相交叉。 例。K5和K3,3都可嵌入于环面上； K3,3可嵌入于Mobius带上；每个图都可“嵌入”于三维空间3

R中。

定理9.2 G可嵌入于平面上 ? G可嵌入于球面上。 证明：利用球极平面射影，略。 #

对偶图

平图G的面（face） ? G将平面划分出来的连通区域的闭包。 外部面（exterior face） ? G中唯一的无界面。

定理9.3. 对平面图G 的任一顶点，都存在G的一个平面嵌入，使它在该嵌入的外部面上。 证明： 先将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** * * f3 G的顶点f1与f2被边e连接

e7f5e6 ? G的面f1与f2 被边e

分隔。

* **

例如，左面所示平图G的对偶图G= (V , E) 为

V* = {f1*，??，f5*} ， E* = {e1* = f1*f5* ， e2* =f5*f5* ，e3* = f2*f5* ，??，e8* = f2*f3*} 。

39

易见，平图G的对偶图G*是一平面图，事实上存在G* 的一个平面嵌入（称为几何对偶）e4e3*

如下：在G的每个面f中放置顶点f，对应于G

e1e2的每一边e，画一条边e* 使它穿过e恰好一次（且f1e8e5ff24不穿过G的其它边）。例如，上例平图G的对偶f3e7图G* 如右图所示。 f5e6*

由上述知，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*f???d?f? ?f?F?G?

*G

定理9.4 设G为平图，则

?d(f)?2?

f?F

证明：左式?G***f?V(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)e?E(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 。

40

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