图论及其应用 doc 南京廖华答案网

图论及其应用 doc 下载本文

文章发布时间 : 2024/5/12 13:20:43星期日

图和子图图和简单图

图 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??)

注判定两个图是否同构是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中两个顶点相邻当且

仅当它们在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}]

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 任一图中，度为奇数顶点的个数为偶数。

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

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

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

[S, S] = G中一端在S中，另一端在S中的一切边的集合。例。（命题）G连通 ? 对任 S ? V 都有 [S, S] ? ? 例。（命题）简单图G中， ? ? k ? G中有长 ? 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)正则简单图。

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的

最后一个公共顶点；而 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 } 。

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

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). 一图的围长（即最短圈的长）。并说明你的算法好到什么程度。

树树

无圈图（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)。

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 。

键（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，有

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的圈的边不重并集；

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中

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

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

...?...

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

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

证明：容易验证，K=AaAa 。又，K的任一行（列）的元素的代数和 = 0，因此 K的所有代数余子式都相等。再，设A k为从A a中去掉第k行所得的 (?-1)?? 矩阵，易见，

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

建设连接 {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

T ? T ? {e}, V? ? V? ? {w}

for all v??V? do //updating L(v) from new vertex w L(v) ? if w(vw) < L(v) then w(vv) end

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条公共边。证明：任何连通图的树图是连通的。

连通度问题连通度

B ? E(G)为图G的k-边割 ? ?B? = k 。

图G的边连通度（edge connectivity)

?'(G)????min{E' E'为G的边割}0当G为非平凡图当G为平凡图

( = 使G变成不连通或平凡图所需去掉的最少边数。）易见，当G为非平凡连通图时， ?? = G的最小键的边数。

?=??=2?=1,??=2?=1,??=2?=??=0?=2,??=3?=??=0例。?? = 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)

??min V' V'为G的点割?(G)????-1???当G有二不相邻接顶点时其它

（ = 使G变成不连通或平凡图所需去掉的最少的顶点数。）

例。当 ? ? 3时， ? = 1 ? G连通且有1-点割。 ?(K?) = ?-1 。

?(G) = ? -1 ? G的基础简单图为完全图。称图G为k-连通的（k-connected） ? ?(G) ? k ? 至少去掉k个顶点才能使G变成不连通或平凡图。例如，所有非平凡连通图都是 1-连通的。

定理3.1 ? ? ?? ? ? 。

证明：先证?? ? ? ：当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(?,?)

d(u,w)= k-1 。

xP因此，由归纳假设，存在二内部不相交的

（u,w)-路P及Q。 uvQw 因G为2-连通，G-w 中一定存在一 (u,v)-路P? 。令x为P?在 P ? Q 中的最后一个顶点。不

P? 失一般性。不妨设x在P上。这时G中有二内部不

相交的(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的块的个数。

v?V3.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 叙述求图的块的好算法。

可靠通信网的建设

? 及??越大越可靠（造价越贵：? ? ?? ? ? ）

问题已给赋权图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与它相邻。考虑图

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 ...e???v??? ，其中，v??? = v0 =u ，v1 =v 。易见

v1 e2 v2 ...e???v??? 就是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 。

假设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）。

又，

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

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

习题

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-因子：

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?。特别地，有

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

完美匹配

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

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有

*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) ，并转到① 。

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

杂性为O(?) )

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

习题

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

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

边着色边色数

前提本章只讨论无环图。

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不能再改进。

引理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 上未表现的（任意取定的）一色；

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

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

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

例。设图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时：则

?(G)= ?-1-?(G)? ? - ?(G) 。

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

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

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

?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 也满足要求；一般，设

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

证明：类似，略。

平面嵌入的慨念可推广到其它平面上。称图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*} 。

易见，平图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?

定理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 。

证明：对? 进行归纳。当? = 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) 。

f?F从而得证。 #

推论9.5.3 设G为简单平面图，则 ? ? 5 。

证明：当? ? 2时显然成立。当? ? 3时，由定理1.1及推论9.5.2有

?? ?

?d(v) = 2? ? 6? - 12 < 6? ，

v?V ∴ ? ? 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 ，

f?F ? ? 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 。

五色定理和四色猜想

定理9.11 (Headwood,1890) 每个平面图是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 ，

则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着色。

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的周界上。

记号 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 1964）

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

~Gi 的面f(4) 选一连接B对Gi的二接触顶点的路Pi ? B。令 Gi+1 = Gi ? Pi。通过把Pi 画在

~中，得 Gi+1 的平面嵌入Gi+1 。

算法证明大意

只要再证对平面图G算法不会停止于(3)。由定理9.14，只要证明算法求出的

G1，G2，??

为G可容许的即可。

~~ 44

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中，得前面的情形① 。

例。判定以下二图的平面性：

1. 块中找一个圈G1。

2. 在G中确定Gi的所有桥及它们对Gi的接触顶点。 3. 对的每个面f确定b(f)。

4. 对每个桥B确定F(B, Gi ) 。

5. 在Gi的某个桥B中，找连接其二接触顶点的路P。上述1. ~ 5. 都有好算法，因此平面性算法是好算法。

习题

9.6.1. 用本节的算法证明Petersen图是非平面图。

算法中要进行的运算为：

~有向图有向图

有向图（directed graph；digraph） D = （V，A）： V(D) —— 顶点集。

u 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） ? 无环、且无二弧其端点及方向相同。

习题

10.1.1. 一个简单图有多少个定向图？ 10.1.2. 证明：

?dv?V?(v) = ? =

?dv?V?(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为头的弧数。

证明：A的第(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在如下意义下是最佳的：对每个（无向）图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的子集）

定理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) ， ??dD(u)?dP(u)?S 。 ???vivi+1

但 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作为工作排序。（有‘好’算法）注。本算法去掉了矩阵[ tij ] 中较大的那一半，因此‘有理由’期望得到较好的结果。当然，这只是一种一厢情愿的想法而已。例如，右图情况下，“去掉了矩阵[ tij ] 中较大的那一半”后，得到的是右图中用直线段构成的竞赛图，其中的最短Hamilton 有向路的长为12；而最优解为4。又，注意到“去掉了矩阵[ tij ] 中较大的那一半”后所得赋权图（包含竞赛图）中求该图的最小权Hamilton 有向路问题，由前述知，仍然是NP-hard 困难问题。

2112110151 2公路系统的单行线化

15101510

问题任给一图G是否有一双向连通定向图？

显然，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和

Word文档下载：图论及其应用 doc.doc

搜索更多:图论及其应用 doc