对于v>1,试给出E= 的不连通简单图 6.3简单图G中,δ>[v2]-1→G连通。当v是偶数时,试给出一个不连通的([v/2]-1) 正则简单图。 .6.4G不连通→G°连通 对任意图G的任一边e,有o(G)≤o(G-e)≤o(G)+1 1.6.6G连通,且d(v)=偶数,Vv∈V→o(G-v)≥d()/2,vv∈V. 1.6.7连通图中,任二最长路必有公共顶点 1.6.8对任一图的任三个顶点u,v,w都有d(u,v)+d(,w)≥du,w) 6.9任一简单图非完全图中,一定有三个顶点u,v,w,使得u,ww∈E而WwgE 闭途径( closed walk)分起点=终点且长>0的途径 闭迹( closed trai1)边各不相同的闭途径。 圈( cycle)分顶点各不相同的闭迹 (可当作一图或子图。) 例。闭途径: uyvyu; uywxywvu; yuyu 闭迹: uy xwyvu 圈 yTvgy"; uywvu。 k-圈(k- cycle)分长为k的圈 例。1-圈(即一条环),2-圈(由重边组成),3-圈(又称 三角形)。 奇圖( odd cycle) 偶圈( even cycle) 定理1.2G为二部图G不含奇圈。 明:→:设G的2-划分为(X,Y),由G的定义,G的任一圈中,X和Y的顶点一定交错出现, 从而其长必为偶数。 :不妨设G为连通的。任取一顶点u,令 X=x∈V丨d(u,x)=偶数} Y=yev|d(u,y)=奇数}。 由于,易见,(X,Y)为V的 划分,只要再证X和Y都是G 的独立集(即X(或Y)中任二 u 顶点v,w都不相邻)即可:令 P与Q分别为最短(u,v)-路与最 短(u,w)-路。设u为P与Q的 最后一个公共顶点:而P与Q分别为P的(u,V)-节与Q的Gu,w)-节。则P与Q只有一公共顶点。 又,由于P与Q的(u,u)-节的长相等,P与Q的长有相同的奇偶性,因此v与w不能相邻,不然, V(P)Qwv 将是一奇圈,矛盾。# 例。(命题)图G中δ≥2→G中含圈。 例。(命题)简单图G,δ≥2→G含长ε≥δ+1的圈。 例。(命题)任一图中 (a)E≥v→含圈。 (b)*.E≥+4→含二条边不重的圈
6 对于 > 1，试给出 = − 1 2 的不连通简单图。 1.6.3 简单图 G 中， > [/2] - 1 G 连通。 当是偶数时，试给出一个不连通的([/2]-1) 正则简单图。 1.6.4 G 不连通 G c 连通。 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。 闭迹：uyxwyvu。 圈： yfvgy ; uywvu。 k-圈（k-cycle） 长为 k 的圈。 例。1-圈（即一条环）， 2-圈(由重边组成），3-圈（又称 三角形）。 奇圈 (odd cycle)。 偶圈 (even cycle)。 定理 1.2 G 为二部图 G 不含奇圈。 证明：：设 G 的 2-划分为（X, Y），由 G 的定义，G 的任一圈中，X 和 Y 的顶点一定交错出现， 从而其长必为偶数。 ：不妨设 G 为 连通的。 任取一顶点 u,令 X = { xV d(u, x) = 偶数 }, Y = { yV d(u, y) = 奇数}。 由于，易见，(X, Y)为 V 的 2-划分，只要再证 X 和 Y 都是 G 的独立集（ 即 X（或 Y）中任二 顶点 v，w 都不相邻 ）即可： 令 P 与 Q 分别为最短(u, v)-路与最 短(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 含二条边不重的圈。 u v y x w e a b d h c f g P Q u P’ Q’ u’ v w
习题 1.7.1若边e在G的一闭迹中,则e在G的一圈中。 17.2证明:(a).ε≥ν→G含圈 (b).E≥v+4→G含两个边不重的圈。 最短路问题 赋权图( weighted g)(权≡1之推广) 权( weight)w(e)≥0 H)=∑w(e),H≤G 路P的长=w(P) 顶点u与v距高d(u,v)=最短(u,v)-路的长。 问题求最短(uo,Vo路 转求最短(uo,)-路,vv∈V\{uo 简化只考虑简单图,且w(e)>0e∈E (w(u)=0时,可合并u与v为一顶点) 原理逐步求出顶点序列 使 d(uo,un)≤ Sk=( uo, ur,u ki =VIS P为最短(uo,u)-路 i=1,2, (1)u:u是使w(uau)=min{w(uo)lv≠uo}者 得S1=S0u{u},P1=uou (2).若已求得Sk-1;duo,u1),d(uo,uk);及最短(uo,u)路P1i=1.2,k-1 uk:显然 d(uo,uk)= min( d(uo,V)I VE S-Ii j)+w(uju 某j∈{1,2,k1} min( d( uo, u)+ w(uuk) uE Sk-1i in(d(uo, u)+ w(uv)I min{l(v)|v∈S-1} 其中 min (d(uo, u)+ wuv)I uE Sk-1i (uk)= d(uo, uk)) Sk-IUfukj 某j∈{1,2,k-1} update进行下一步时,只要更新l(v)即可: (v)< minI(v), I(uk)+w( ukv)i vv∈ Dijkstra算法 (1)作为开始:I(uo)←0;l(v)← v≠u0 (2).(这时己有Sk={uo,u,uk}) I(v)< min ((v), I(uk)+w(uv)j 再计算min{(v)},设其最小值点为uk+1,令 Sk+1=SkU{uk+1}
7 习题 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 e E H ( ) ( ) , H G . 路 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=V-1,仃止:不然,令k←k+1,并回到(2) L 计算复杂性 6 比较:v(v1)/2×2 凡是复杂性为p(v,E)的算法(p(,)为一多项式)称为“好算法”(“good algorithm”- J. Edmonds)。这是相对于指数型算法而言的:在10-6秒/步运算速度下: 复杂性 008sec 027sec 125sec 24. 3sec 5.2min 17. 9min 12. 7days 35.7years 由上表可见,两种算法有天壤之别。 注1若只关心求d(uo,vo)则算法进行到vo∈Sk时停止。 2.计算过程中,所得子图是一棵树。每步都是往其上增加一条边及一个顶点,因此该过程称为 tree growing procedure 3.若要计录u到每个顶点u的最短路,只要记录下该路中u的前一个顶点即可 习题 1.8.1描述一个算法以确定 (a).一图的各个分支 图的围长(即最短圈的长)。 并说明你的算法好到什么程度 树树 无圈图( acyclic g.;林 forest)。 树(tree)连通无圈图 叶( leave)树中度为1的顶点 定理2.1树中任二顶点间有唯一的路相连 证明:反证,假设存在树G,其中有二顶点u与v,其间有二不同(u,ⅵ)-路P和P2相连。因P1≠ P2,一定存在P的一条边e=xy,它不是P2的边。显然,图P∪P2-e是连通的,从而其中包含 条(x,y)-路P。于是P+e是G中的一圈,这与G为无圈图相矛盾。 注意(1).当G无环时,易见 G是树G中任二顶点间有唯一的路相连 (2).以下结论不一定成立:彐闭途径→彐圈
8 (3). 若 k = - 1 , 仃止；不然，令 k k+1 ,并回到 (2) 。 计算复杂性 加法： (- 1)/2 比较： (- 1)/2 2 v S ： (-1)2 +)________________________________________________ 共 O ( 2 ) 凡是复杂性为 p( , ) 的算法 ( p( . , . ) 为一多项式 ) 称为“好算法”( “good algorithm”------J.Edmonds )。这是相对于指数型算法而言的：在 10 - 6 秒/步运算速度下： 复杂性 n= 10 20 30 40 50 n 3 .001sec .008sec .027sec .064sec .125sec n 5 .1sec 3.2sec 24.3sec 1.7min 5.2min 2 n .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). 以下结论不一 定成立： 闭途径 圈 。 7 2 2 1 3 2 1 7 3 5 3 4 4 4 8 6 6 u0 u0 uj v uk Sk-1 Sk-1 Sk
定理2.2G是树 E=V-1。 证明:对ν进行归纳。当Vv=1时,G=K1,成立。假设定理对小于v个顶点的树成立,而G 为ν个顶点的树。任取G的一边uv。它是G中的一条路,由定理2.1知 G-uv不连通, 且它恰有二分支(习题1.6.5),设为G,与G2。它们都是连通无圈图,因此是树。又,它们的顶点数 都小于v。由归纳假设知 E(G1)=v(G:)-1 =1.2 E(G)=ε(G1)+ε(G2)+1 (G,)+v(G2) (G)-1 推论2.2每棵非平凡树至少有两个度为1的顶点。 明:由于G为非平凡连通图, d(v)≥1 再由定理1.1及2.2知, ∑4(v)=2E=2v-2 由此知推论成立 例。(命题)恰只包含二度为一顶点的树是路 习题 2.1.1证明:非平凡树中,任一最长路的起点和终点均是度为1的顶点。再由此去证明推论2.2。 2.1.2当ε=-1时,证明以下三结论是等价的: (a)G是连通图 (b)G是无圈图 c)G是树。 2.1.3一树中若△≥k,则其中至少有k个度为1的顶点 2.1.4G为林ε=v-0。 2.1.5若林G恰有2k个奇点,则G中存在k条边不重的路P,P2,.P,使得 E(G)=E(P1)UE(P2)∪...∪E(P)。 21.6正整数序列(d,d2,…,d)是一棵树的度序列,当且仅当∑d=2(v-1) 2.1.7饱和烃分子形如CHn,其中碳原子的价键为4,氢原子的价键为1,且任何价键序列都不 构成圈。证明:对每个m,仅当n=2m+2时cH,方能存在 割边和键 e为割边( cut edge)eo(G-e)>o(G) (即o(G-e)=o(G)+1) 定理2.3e为G的割边分e不在G的任一圈中 证明:令e=xy,则x与y在G的同一分支中。于是 e为G的割边 台x与y不Ge在同一分支中 G-e中无(x,y)-路 分G中无含e的圈 定理2.4图G连通,且每边是割边分G为树
9 定理 2.2 G 是树 = - 1。 证明：对 进行归纳。当 = 1 时，G = K 1 ，成立。假设定理对 小于 个顶点的树成立，而 G 为 个顶点的树。任取 G 的一边 uv 。它是 G 中的一条路，由定理 2.1 知， G - uv 不连通， 且 它恰有二分支（习题 1.6.5），设为 G1 与 G2 。它们都是连通无圈图，因此是树。又，它们的顶点数 都小于 。由归纳假设知 (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 v V ( ) = 2 = 2 − 2 ， 由此知推论成立。 例。（命题）恰只包含二度为一顶点的树是路。 习题 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 i= = − 1 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为极小( minima)连通生成子图(意指T的任一真子图都不是连通生成子图)(由定 义,T可在保持连通性的前提下,用逐步从G中去边(∴所去的边一定在一圈中(即非割边)(每次 破坏一圈)的办法求出。 由T的定义知,o(T)=1, (T-e) 即T的每边为割边,故由定理2.4知T为树。 注也可用极大无圈(生成)子图(即其真生成母图都含圈)来求生成树T。它可由V上的空图开 始,在保持无圈的前提下,逐步由G中取边的办法求出。(为何是生成树?) 推论2.4.2G→ε≥V-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连通,且ε=v- G连通。且ε=v-1。 图G的边铡( edge cut)[s,S G中一端在S另一端在S中的边的子集合 显然,在连通图G中, E’→边割o(G-E”)>1。 键(bond,割集 cut set) 极小非空边割 例。e是G的割边{e}是G的键。 例。左图G中 w luv, zv, zyl [zu, zv, zyl 都是边割,其中后两个为键。而E={zu,zv,zy,uvl 不是G的边割,当然更不是G的键,虽然GE变成不连 通。 易见,当G连通且S≠时 边子集B为G的键B是使G不连通的E的极小子集。 台o(G-B)=2,且中每边的两端点分别在二分支中。 边 割B=[S,S]为键G[s],G[S]都连通。(习题) 设H为G的子图,称子图G-E(H)为G中H的补图,记为
10 证明：注意到以下事实即可， 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}, {zu, zv, zy, xy, xw}, {uv, zv, zy} {zu, zv, zy} 都是边割，其中后两个为键。而 E’ ={zu, zv, zy, uv} 不是 G 的边割，当然更不是 G 的键，虽然 G- E’ 变成不连 通。 易见，当 G 连通且 S 时， 边子集 B 为 G 的键 B 是使 G 不连通的 E 的极小子集。 (G-B)=2，且中每边的两端点分别在二分支中。 边 割 B = [S, S ]为键 G[S],G[ S ]都连通。 （习题） 设 H 为 G 的子图，称子图 G - E(H) 为 G 中 H 的补图，记为： u v w z y x