《图论及其应用》主要知识点讲义讲解

H(G 特别地,当T为G的生成树时,称 T 为G的余树。 定理2.6设T为连通图G的一个生成树,e为T 的一条边,则 1).余树T不包含G的键; G (2).T+e中唯一包含的G的一个键 证明:(1).因G )=T连通,则T不包含G的边割,从而也不包含G的键。 (2).注意到e为的T割边,令S与S分别为T-e的二分支的顶点集。考虑 B= [S, S 由于G[S](包含T-e的一个分支T[s])与G[](包含T-e的一个分支T[剂])都连通,B必是 G键,包含于T+e中 来证B为包含在T+e中的唯一键,只要再证对包含在Te中的G的任一键B',一定有B=B 即可:假设不然,由于键的极小性,B不会包含B,从而一定存在B的一边b∈B。于是 G-B’T-e+b(注意到B'cT+e→G-B’2T-e) 但T-e+b也是G的一生成树(因其边数=v-1,且连通),从而G-B’连通,这与B’为G的键相 矛盾。 附录设G连通,T为其任一生成树 对每一e∈T,T+e中有唯一圈C,因而可得 共E-V+1个不同的圈,每个称为G的一个基本圈。 同样,对每一e∈T,T+e中有唯一的键因而可得 B1,B2, B 共v-1个不同的键,每个称为的一个基本割集 设S1,S2为二集合,记其对称差(即(SS2)-(S∩S2))为 S, Sz 称为它们的环和( r ing sum) 性质 1)图G的每一边割是G的一些割集的边不重并。 2)设B1,B2为图的任二边割,则B1⊕B2也是G的边割。(对任二非空V,V2cV,有 [V,V]e[V,v]=[v2,V2],其中V3=(V1∩V2)∪(V∩V2))。 3)设边子集E与E”分别为G中一些圈的边不重并,则EeE”亦然。 4)G的每个圈可唯一地表为G的一些基本圈的环和 5)G的每个边割可唯一地表为G的一些基本割集的环和 6)边子集E为G中一些边不重圈的并集 边子集E与G中每个边割有偶数条公共边 7)边子集B为G的一个边割 边子集B与G的每个圈有偶数条公共边 8)G为一些圈的边不重并d()=偶数 yv∈V 习题 2.2.1设G连通且e∈E,证明: (a)e在G的每棵生成树中当且仅当e是G的边割 (b)e不在G的任一生成树中当且仅当e是G的环。 2.2.2无环图G恰只有一棵生成树T,则G=T 2.2.3设F是G的极大( max ima I)林,证明: (a)对G的每个分支H,F∩H是H的生成树

11 H(G) 。 特别地，当 T 为 G 的生成树时，称 T 为 G 的余树。 定理 2.6 设 T 为连通图 G 的一个生成树， e 为 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， 有 [V1 ,V1][V,V] = [V2 , V2], 其中 V3 =(V1 V2)(V1 V2 ) ）。 3) 设边子集 E’与 E”分别为 G 中一些圈的边不重并，则 E’E” 亦然。 4) G 的每个圈可唯一地表为 G 的一些基本圈的环和。 5) G 的每个边割可唯一地表为 G 的一些基本割集的环和。 6) 边子集 E’为 G 中一些边不重圈的并集  边子集 E’与 G 中每个边割有偶数条公共边。 7) 边子集 B 为 G 的一个边割  边子集 B 与 G 的每个圈有偶数条公共边。 8) G 为一些圈的边不重并  d(v) = 偶数  v  V 习题 2.2.1 设 G 连通且 e  E，证明： (a) e 在 G 的每棵生成树中当且仅当 e 是 G 的边割。 (b) e 不在 G 的任一生成树中当且仅当 e 是 G 的环。 2.2.2 无环图 G 恰只有一棵生成树 T，则 G = T 。 2.2.3 设 F 是 G 的极大（maximal）林，证明： (a) 对 G 的每个分支 H， FH 是 H 的生成树； G T T

(b)(F)=v(G)-o(G) 2.2.4证明:任一图G至少包含E-ν+o个不同的圈 2.2.5(a)若G的每个顶点均为偶点(即,度为偶数的顶点),则G没有割边 (b)若G是k-正则偶图且k≥2,则没有割边 226当G连通且S≠②时, 边割B=[S,S]为键分G[S].G[S]都连通 2.2.7图G的每一边割是G的一些键(即,割集)的边不重并 2.2.8在图G中,设B1和B2为键,C1和C2为圈(看作边子集)。证明: (a)BGB2是G的键的边不重并集 (b)C,GC2是G的圈的边不重并集 (c)对G的任一边e,(B1B2)\{e都包含键 (d)对G的任一边e,(C∪C2)\{e都包含圈 2.2.9证明:若图G包含k棵边不重的生成树,则对于顶点集每一划分V1,V2,,V),端点在这 个划分的不同部分的边的数目至少为k(n-1)。 割点 称顶点v为G的割点( cut vertex)E可划分为二非空子集E1及E2,使G[E1]与G[E2只有 公共顶点v 显然,当G无环时, v为割点o(G-v)>o(G) 台存在二顶点x及y,使G中任一(x,y)-路一定包含v 例。(边割) 为G的键不是的G的割点 定理2.7在树G中 v为割点分d()>1 证明:(i)若d(v)=0,则G≡K1,v不是割点。 (ii)若d(v) 则G-v仍然是树。因此o(G-v)=1=o(G),从而不是割点 (i)若d(v)>1,则G中存在与v相邻接的二不同顶点u,w。由定理2.1知,uw是G 中的唯一(u,w)-路,因此G~v中不含(u,w)-路,(即Gv中u,w不连通) 即v为G的割点 推论2.7非平凡、无环、连通图中,至少有二顶点不是割点 证明:令T为G的一生成树,由推论2.2及定理2.7知,T中至少存在二顶点u与v不是T的割点 则它们也不是G的割点:这是因为对于u(及v有 1=(T-u)≥(Gu)≥1 0(G-u)=1=0(G) 习题 2.3.1设G为v≥3的连通图,证明 (a)若G有割边,则G有顶点v使o(G-v)>o(G); (即,割边必有一端点为割点) (b)(a)的逆命题不成立

12 (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)。 割点 称顶点 v 为 G 的割点(cut vertex)  E 可划分为二非空子集 E1及 E2，使 G[E1]与 G[E2]只有一 公共顶点 v。 显然， 当 G 无环时， v 为割点  (G-v) > (G) 。  存在二顶点 x 及 y ，使 G 中任一(x, y)-路一定包含 v。 例。（边割）     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)的逆命题不成立。 G E1 E2

2.3.2证明:恰有二顶点为非割点的简单连通图必是一条路。 233在简单连通图G中证明 v为G的割点G的任一生成树不以v为叶。 生成树的计数及 Caley公式 本节只讨论无环连通图。 将图G的关联Ax矩阵中每列的两个1元素之一改为-1,得一新矩阵,记为A。(它是G的一个定 向图的关联矩阵)。例如: VI 0 =,0 0 0 记A为从A中删去某一行所得的(v-1)×E矩阵。 引理1设A,为A的任一(y1)阶子方阵,则 det(A)=±1A1的列对应于G的一生成树 证明:令划去的行对应于顶点u,记H为以全体与A的列相对应的边构成的生成子图。由于cE(H) v1,因此有 H连通 H为G的生成树 (1)当H不是G的生成树时,由上述知,H不连通。令S为H中不含u的一个分支的顶点集。易 见,A中对应于S的全体行向量之和为一零向量。因此,det(A1)=0 (2)当H是G的生成树时,重排A的行、列如下: 取H的一个度为1的顶点u1,并使u1≠u。记u1在H中的关联边为e1;再取Hu 中的一个度为1的顶点u2,并使u2≠u,记u在Hu中的关联边为 的顺序重排A,的行、列,得矩阵A,’。易见,A',为下三角型。且主对 角线元素全为±1,因此detA|=detA=1。 # inet- auchy定理设矩阵P=[p]。xn,Q[q]n,且m≤n则 P1i. q deu(Pg)=∑ Isi<<j sn pmg, 引理2连通图的生成树数目=det(AA) 证明:由 Binet- Cauchy定理知 det(AA)=∑(detA)2(对A的所有v-1阶子方阵A求和) 但由引理1知 ±11的列对应于G的一生成树 detAl 其它 得证。 无环图G的度矩阵 k=[k;i Jvx 其中 当i≠且v与v,间有n条平行边 ld(v)

13 2.3.2 证明：恰有二顶点为非割点的简单连通图必是一条路。 2.3.3 在简单连通图 G 中证明： v 为 G 的割点  G 的任一生成树不以 v 为叶。 生成树的计数及 Caley 公式 本节只讨论无环连通图。 将图 G 的关联 A 矩阵中每列的两个 1 元素之一改为 -1，得一新矩阵，记为 Aa（它是 G 的一个定 向图的关联矩阵）。例如： A e e e e e v v v v a = − − − − −             1 2 3 4 5 1 2 3 4 1 1 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 记 A 为从 Aa 中删去某一行所得的( -1) 矩阵。 引理 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 p p p p q q q q ij j mj mj j j m j j m j j n m m m m m =       1 1 1 1 1 1 1 1 1 引理 2 连通图的生成树数目 = det（AAT）。 证明：由 Binet-Cauchy 定理知， det(AAT ) = ∑(detA1) 2 (对 A 的所有 v-1 阶子方阵 A1 求和） 但由引理 1 知 detA1 =  1 0 A1的列对应于G的一生成树 其它 得证。  无环图 G 的度矩阵 K = [ kij ]   ， 其中 k i j v v d v i j ij ij i j ij i = −  =     当 且 与 间有 条平行边 ( ) 当 v1 v2 v4 v3 e1 e2 e3 e4 e5

例如对本节开头的例子有 定理连通图G的生成树数目=K的任一元素的代数余子式 证明:容易验证,K=AA。又,K的任一行(列)的元素的代数和=0,因此K的所有代数余 子式都相等。再,设A为从A中去掉第k行所得的(y1)×E矩阵,易见, AAk=从K中去掉第k行第k列后所得的子方阵 故由引理2知本定理成立 例。前例的图的生成树数目=K的(2,3)-元素的代数余子式 2 (-1)240 8 1 定理( Cayley)Kn中共有n2个不同的生成树 证明:用上述定理可直接证出(习题 习题 2.4.1求Ks,3的生成树数目。 24.2若e是Kn的一条边,则K。-e的生成树数目为(n-2)n"3。 连线问题 问题设城市v;与v间建立直接通信线路的费用为c;(≥0) 建设连接{v,V2…,v,}的通讯网使造价最省 在赋权图G中求一最小权连通生成子图 在赋权图G中求一最小权生成树(最优树)。 下面的 Kruskal算法是在非赋权图中求生成树的“极大无圈子图”算法的改进,它是一种贪心算法 (greedy al gor ithm Kruskal's al gor ithm (1)选棱(link)e1使w(e1)最小; (2)若已选定e e;,则从E\e;,ea,.,e}中选取e;,使 (i) G[e,, ez e;Jle;]无圈 (i)w(e;…)是满足(i)之最小者。 (3)若(2)不能再进行下去时,停止。否则,回到(2)。 定理2.10 Kruskal算法求出的生成树 G[{e1,e2,.ew-1J] 是最优树。 证明:反证,假设T不是G的最优树。取G的一最优树T。令e为 顺序)第一个不属于T的边,且令T为最优树中使k为最大者。则T+e中唯一的圈G包含e,且C中 必含一条边e*gT'(不然,CcT,矛盾。)但 T’=T+e-e’k

14 例如对本节开头的例子有 K v v v v v v v v = − − − − − − − − − −             1 2 3 4 1 2 3 4 2 1 0 1 1 3 1 1 0 1 2 1 1 1 1 3 定理 连通图 G 的生成树数目 = K 的任一元素的代数余子式 证明：容易验证，K=AaAa T 。 又，K 的任一行（列）的元素的代数和 = 0，因此 K 的所有代数余 子式都相等。 再，设 A k 为从 A a 中去掉第 k 行所得的 (-1) 矩阵，易见， A kA T k = 从 K 中去掉第 k 行第 k 列后所得的子方阵 故由引理 2 知本定理成立。  例。前例的图的生成树数目 = K 的(2,3)-元素的代数余子式 = (− ) − − − − − − + 1 2 1 1 0 1 1 1 1 3 2 3 = 8 。 定理（Cayley） K n 中共有 n n-2 个不同的生成树。 证明：用上述定理可直接证出（习题）。  习题 2.4.1 求Ｋ３，３的生成树数目。 2.4.2 若ｅ是Ｋｎ的一条边， 则 Ｋｎ－ｅ的生成树数目为 (n-2)nn-3 。 连线问题 问题 设城市 vi 与 vj 间建立直接通信线路的费用为 cij（  0）。 建设连接 { v v v 1 2 , ,......,  }的通讯网使造价最省  在赋权图 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 v1 v2 v4 v3 e1 e2 e3 e4 e5

也是G的生成树。(因ek不是T+e的割边(定理2。3),从而T连通,且其边数=V-1。)又, 由于T的子图 G[e,, ex,..., e-u e, 1I 也不含圈,由法算法知 w(e4)≤w(e’) W(T)≤w(T), 即T'也是G的最优树,且{e;,e2,,ev-}中第一个不属于T的边的下标>k。这与k的取法相 矛盾 # 实现先按权的不减顺序将边集重排成 关于算法中无圈性的判定,我们有一简单的办法:当S={e1,e2,,e;}已取定时,对候选边 G[S∪{a}]无圈a的两端点在林G[s](此处当作生成子图)的 不同分支中。 从而我们有求最优树的标记法 开始:取a1为候选边:并将ⅵ标以k,k=1,2,v。 若S={e1 e;}己取定,当候选边a的两端点有相同标号时,改取an为候选边(丢 掉a永不再考虑);否则选定e=a,并将G[S]中a两端点所在的二分支的顶点重新标号,标以两者 中的最小者。 算法复杂性 边排序 o( Eloge 比较边两端的标号E 重新标号 0((V-1)v) 故为好算法(≤0(2))。 34/3 附录 (A) Pr ims al gor ithm(也是一种贪心算法) T←,V for alI v∈V'doL(v)←w(uv)∥/ initial izing L(.) beg ir find vertex w s t. L(w)=minI L()IVE V nd denote the associated edge from v to w by e T←T∪le},V←Vu{w for alI v∈v’do //updating L(v) from new L(v)< if wvw)< L(v) then w(v Prim算法的复杂性为0(v) (B) Steiner tree prob (NP-hard prob. 已给赋权连通图G中,任给定VcV,求一最小权树T使V(T)=V 习题 25.1用 Kruskal|算法解带约束的连线问题:用最小费用建立一连接若干城市的网络。但某些特 定的城市对间要求有直通线路相连 25.2连通图G的树图是这样的一个图:其顶点集是G的全体生成树{T,T2,,T},且 T,和T相连它们恰有v-2条公共边 证明:任何连通图的树图是连通的

15 也是 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 ) 比较边两端的标号  重新标号 O((  -1) ) 故为好算法（  O(  3 ) ）。 附录 （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( 2 ) （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 条公共边。 证明：任何连通图的树图是连通的。 6 2 3 1 8 6 6 3 7 2 3 4 例