记号 对任一非 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