图论及其应用.doc

图和子图图和简单图 图 G = (V, E)， 其中 V = V -顶点集， -顶点数 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）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。 一条边的端点：它的两个顶点。 记号：。习题1.1.1 若G为简单图，则 。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。注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。注 判定两个图是否同构是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 。类似地可定义，完全三部图（例如 Km,n,p），完全 n-部 图等。例。用标号法判定二部图。习题1.2.1 G H n(G) = n(H) , e(G) = e(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).e(Km,n ) = mn ; (b). 对简单二部图有 e n2/4 .1.2.6 记Tm,n为这样的一个完全m-部图：其顶点数为n，每个部分的顶点数为n/m或n/m个。证明： (a). e(Tm,n) = 其中 k =n/m . (b)*. 对任意的n顶点完全m-部图G，一定有 e(G) e(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是自补的，则 n 0, 1 (mod 4) 关联矩阵M(G)与邻接矩阵A(G)M(G)=mi,jn*e,A(G)=ai,jn*n ,其中 mi,j = 顶点vi与边ej 的关联次数= 0, 1, 2. ai,j = 连接顶点vi 与 vj 的边数 。 例。 子图子图(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.）GV, (非空V V ) 以V为顶点集，以G中两端都在V上的边全体为边集构成的G的子图。边导出子图 GE 非空E E 以E为边集，以E中所有边的端点为顶点集的的子图。例。以上两种子图，其实，对应于取子图的两种基本运算。下面是取子图的另两种基本运算：G - V 去掉V及与V相关联的一切边所得的剩余子图。 即 GV VG - E 从中去掉E 后所得的生成子图例。G - b, d, g, ( = GE b, d, g ) G - b, c, d, g, ( GE b, c, d, g ) G - a, e, f, g. ( GE a, e, f, g )注意 GE 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仍可能为相交的）。并图 G1G2 , 当不相交时可简记为 G1+G2. 交图 G1G2 .习题1.4.1 证明：完全图的每个导出子图是完全图；偶图的每个导出子图是偶图。1.4.2 设G为一 完全图，1 n 0)的2-划分为 (X, Y),则 |X| = |Y|。1.5.3 在人数 1的人群中，总有二人在该人群中有相同的朋友数。1.5.4 设V(G) = ，则称 ( d(v1), d(v2), . , d(vn) ) 为G的度序列。证明：非负整数序列 ( d1 ,d 2, ., d n) 为某一图的度序列 是偶数。 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 。终点（terminus） x。内部顶点（internal vertex） y, v, w, x。 （注意，中间出现的x也叫内部顶点。）长 边数（重复计算）。节（段，section）。 例如W的(y, w)-节=yvw 。W-1 （逆途径）, WW（两条途径W与W相衔接）。迹( trail) 边各不相同的途径。 例如，yvwyx 。路 (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划分为（等价类）：V1,.,Vw使每个Vi中的任二顶点u及v都连通（即存在(u, v)-路）。 称每个GVi i=1,2,.w为G的一个分支（component）; 称w(G）为G的分支数。G为连通图 w(G) = 1 G中任两点间都有一 条路相连。G为非连通图 w(G) 1。记号 对任一非空 SV ，令 = VS, 记（称为边割） S, = G中 一 端在S中，另一 端在中 的一切边的集合。例。（命题）G连通 对任 S V 都有 S, 例。（命题） 简单图G中， d k G中有 长 k 的路。习题1.6.1 证明：G中长k为的(vi ,vj )-途径的数目, 就是A k中的(I, j)元素。1.6.2 证明：对简单图G有， G连通。对于n 1，试给出的不连通简单图。1.6.3 简单图G中， d n/2 - 1 G连通。 当n是偶数时，试给出一个不连通的(n/2-1)正则简单图。1.6.4 G不连通 Gc 连通。1.6.5 对任意图G的任一边e，有 w(G) w(G-e) w(G) +1 。 1.6.6 G连通，且 d(v)=偶数， v V w(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不能相邻，不然，页码: 6 v( P)-1 Qwv将是一 奇圈，矛盾。#例。（命题） 图G中 d 2 G中含圈。例。（命题） 简单图G，d 2 G含长 e d+1 的圈。例。（命题） 任一图中 (a). e n 含圈。 (b)*. e n + 4 含二条边不重的圈。习题1.7.1 若边e在G的一闭迹中，则e在G的一圈中。1.7.2 证明：(a). e n G含圈。 (b)*. e n + 4 G含两个边不重的圈。最短路问题赋权图（weighted g.)(权 1 之推广 ) 权( weight ) w(e) 0. w(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 ， = V S 。 Pi为最短( u0, ui)-路 i= 1, 2,.(1).u1 ： u1是使 w(u 0u1) = min w(u 0v) v u 0 者 . 得 S1 = S0u1 , 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 = 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 = mind( u 0 , u ) + w(uv ) | v , u S k-1 = min l( v ) | v 其中， 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 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 再计算 min l( v ) ，设其最小值点为 u k+1 ，令 S k+1 = S k u k+1 。(3). 若 k = n - 1 , 仃止；不然，令 k k+1 ,并回到 (2) 。计算复杂性 加法： n(n- 1)/2 比较： n(n- 1)/2 2 v ： (n-1)2 +)_ 共 O (n2 )凡是复杂性为 p( n, e ) 的算法 ( p( . , . ) 为一多项式 ) 称为“好算法”( “good algorithm”-J.Edmonds )。这是相对于指数型算法而言的：在10 - 6秒/步运算速度下：复杂性 n= 1020304050n3.001sec.008sec.027sec.064sec.125secn5.1sec3.2sec24.3sec1.7min5.2min2n.001sec1.0sec17.9min12.7days35.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是树 e = n - 1。证明：对 n 进行归纳。当 n = 1时，G = K 1 ，成立。假设定理对 小于 n个顶点的树成立，而G为 n 个顶点的树。任取G的一边uv 。它是G中的一条路，由定理2.1知， G - uv 不连通，且 它恰有二分支（习题1.6.5），设为G 1与G 2 。它们都是连通无圈图，因此是树。又，它们的顶点数都小于 n 。由归纳假设知 e(G I ) = n(G I )- 1 I= 1,2 .故， e(G) = e(G 1 ) + e(G 2 ) + 1 = n(G 1 ) + n(G 2 ) - 1 = n(G) - 1 。 # 推论2.2 每棵非平凡树至少有两个度为1的顶点。证明：由于G为非平凡连通图， d(v) 1 , v V 。再由定理1.1 及2.2知， ，由此知推论成立。例。（命题）恰只包含二度为一顶点的树是路。习题2.1.1 证明：非平凡树中，任一最长路的起点和终点均是度为 1的顶点。再由此去证明推论2.2。2.1.2 当 e = n - 1 时，证明以下三结论是等价的： (a) G 是连通图； (b) G是无圈图； (c) G是树。2.1.3 一树中若 D k，则其中至少有k个度为 1 的顶点。2.1.4 G为 林 e = n - w 。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 n )是一 棵树的度序列，当且仅当。2.1.7 饱和烃分子形如C mH n ,其中碳原子的价键为4，氢原子的价键为 1，且任何价键序列都不构成圈。证明：对每个m，仅当n = 2m + 2时C mH n方能存在。 割边和键e为割边( cut edge) w(G-e) w(G) 。 （即 w(G-e) = w(G) + 1 ）定理2.3 e为G的割边 e不在G的任一圈中 。证明：令 e = xy ，则 x 与 y在G的同一分支中。于是，e 为G的割边 w(G-e) = w(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的定义知， w(T) = 1 ，w(T - e) = 2 e E(T) 。即 T 的每边为割边，故由定理2.4知T为树。 # 注 也可用极大无圈（生成）子图（即其真生成母图都含圈）来求生成树 T。它可由V上的空图开始，在保持无圈的前提下，逐步由G中取边的办法求出。 （为何是生成树？）推论2.4.2 G e n - 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连通，且 e = n - 1 G连通。且 e = n - 1 。图G的边割（ edge cut） S, S V G中一端在S另一端在中的 边的子集合。显然，在连通图G中，E 边割 w(G-E) 1 。 键（bond, 割集cut set ) 极小非空边割。例。e是G的割边 e 是G的键。例。左图G中，uv, zv, zy, vw, yx,zu, zv, zy, xy, xw,uv, zv, zyzu, zv, zy都是边割，其中后两个为键。而 E =zu, zv, zy, uv不是G的边割，当然更不是G的键，虽然G- E 变成不连通。易见，当G连通且 S 时， 边子集B 为G的键 B是使G不连通的E的极小子集。 w(G-B)=2，且中每边的两端点分别在二分支中。 边割B = S,为键 GS,G都连通。 （习题）设H为G的子图，称子图 G - E(H) 为G中H的补图，记为：H(G) 。特别地，当T为G的生成树时，称T为G的余树。 定理2.6 设T为连通图G的一个生成树， e为T的一条边，则(1).余树T 不包含G的键；(2). T + e中唯一包含的G的一个键。证明：(1).因 G - E(T )= T 连通，则不包含G的边割，从而也不包含G的键。(2).注意到e为的T割边，令S与S 分别为 T - e的二分支的顶点集。考虑B = S,SG由于GS ( 包含T-e的一个分支TS) 与GS ( 包含T-e的一个分支TS) 都连通，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的一生成树（因其边数=n -1，且连通），从而G - B 连通，这与B 为G的键相矛盾。 # 附录 设G连通，T为其任一生成树。对每一 e T ，T+e 中有唯一圈C，因而可得C1 ,C2 ,.,Ce-n+1 共e -n + 1个 不同的圈 ，每个称为G的一个基本圈。同样，对每一 e T ，T+e中有唯一的键因而可得 B1 ,B2 ,.,Bn-1 共n - 1个不同的键，每个称为的一个基本割集。设S1 ,S2为二集合，记其对称差( 即（S1S2）-（S1S2） )为S1 S2 称为它们的环和(ring sum)。 性质 1) 图G的每一边割是G的一些割集的边不重并。2) 设B1 ,B2 为图的任二边割，则B1 B2 也是G的边割。 （对任二非空V1 ,V2 V， 有V1 ,V1V,V = V2 , V2, 其中V3 =(V1 V2)(V1 V2 ) ）。3) 设边子集E与E”分别为G中一些圈的边不重并，则EE” 亦然。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， FH 是H的生成树；(b) e(F) = n(G)- w(G)。2.2.4 证明： 任一图G至少包含 e - n + w 个不同的圈。2.2.5 (a) 若G的每个顶点均为偶点（即，度为偶数的顶点），则G没有割边； (b) 若G是k-正则偶图且 k 2，则没有割边。2.2.6 当G连通且 S 时， 边割B = S,为键 GS,G都连通。2.2.7 图G的每一边割是G的一些键（即，割集）的边不重并。2.2.8 在图G中，设B1和B2为键，C1和C2为圈（看作边子集）。证明：(a) B1B2 是G的键的边不重并集；(b) C1C2是G的圈的边不重并集；(c) 对G的任一边e，(B1B2)e都包含键；(d) 对G的任一边e，(C1C2)e都包含圈。2.2.9 证明：若图G包含k棵边不重的生成树，则对于顶点集每一划分(V1 ,V2 ,.,Vn )，端点在这个划分的不同部分的边的数目至少为 k(n-1)。 割点称顶点v为G的割点(cut vertex) E可划分为二非空子集E1及E2，使GE1与GE2只有一公共顶点v。显然， 当G无环时，v为割点 w(G-v) w(G) 。 存在二顶点x及y ，使G中任一(x, y)-路一定包含v。例。（边割） 为G的键 v不是的G的割点。定理2.7 在树G中v为割点 d(v) 1 。证明：(i) 若d(v) = 0，则G K1 ，v不是割点。 (ii) 若 d(v) = 1，则G -v 仍然是树。因此 w(G-v)= 1 = w(G)，从而 v不是割点。 (iii) 若 d(v) 1，则G中存在与v相邻接的二不同顶点u, w 。由定理2.1知，uvw是G中的唯一(u, w)-路，因此G-v中不含(u, w)-路，（即G-v中u,w不连通） w(G-v) 1 ，即v为G的割点。 # 推论2.7 非平凡、无环、连通图中，至少有二顶点不是割点。证明：令T为G的一生成树，由推论2.2及定理2.7知，T中至少存在二顶点 u与v不是T的割点，则它们也不是G的割点：这是因为对于u (及v)有1 = w(T-u) w(G-u) 1 ， w(G-u) = 1 =w(G) 。 # 习题2.3.1 设G为 n 3的连通图，证明：(a) 若G有割边，则G有顶点v使 w(G-v) w(G)； （即，割边必有一端点为割点）(b) (a)的逆命题不成立。2.3.2 证明：恰有二顶点为非割点的简单连通图必是一条路。2.3.3 在简单连通图G中证明：v为G的割点 G的任一生成树不以v为叶。 生成树的计数及Caley公式本节只讨论无环连通图。将图G的关联Ane 矩阵中每列的两个1元素之一改为 -1，得一新矩阵，记为Aa（它是G的一个定向图的关联矩阵）。例如： 记A为从Aa中删去某一行所得的(n -1)e 矩阵。引理1 设A 1 为A的任一(n-1) 阶子方阵，则det(A1 ) = 1 A1 的列对应于G的一生成树。证明：令划去的行对应于顶点u，记H为以全体与A1的列相对应的边构成的生成子图。由于 e(H)= n-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 。易见，A1 为下三角型。且主对角线元素全为 1 ,因此 |detA1 | = |detA1| =1 。 # Binet-Cauchy定理 设矩阵 P= pij mn ， Q= qij nm ，且m n 则引理2 连通图的生成树数目 = det（AAT）。证明：由Binet-Cauchy定理知，det(AAT) = (detA1)2 (对A的所有 v-1阶子方阵A1求和）但由引理1知|detA1| = 得证。 # 无环图G的度矩阵 K = kij n n ， 其中例如对本节开头的例子有定理 连通图G的生成树数目 = K的任一元素的代数余子式证明：容易验证，K=AaAaT 。 又，K的任一行（列）的元素的代数和 = 0，因此 K的所有代数余子式都相等。 再，设A k为从A a中去掉第k行所得的 (n-1)e 矩阵，易见，A kAT k = 从K中去掉第k行第k列后所得的子方阵故由引理2知本定理成立。 # 例。前例的图的生成树数目 = K的(2,3)-元素的代数余子式= = 8 。定理（Cayley）K n 中共有nn-2 个不同的生成树。证明：用上述定理可直接证出（习题）。# 习题2.4.1 求，的生成树数目。2.4.2 若是的一条边，则的生成树数目为(n-2)nn-3 。 连线问题问题 设城市vi与vj间建立直接通信线路的费用为cij（ 0）。建设连接 的通讯网使造价最省 在赋权图G中求一最小权连通生成子图； 在赋权图G中求一最小权生成树（最优树）。下面的Kruskal算法是在非赋权图中求生成树的“极大无圈子图”算法的改进，它是一种贪心算法（greedy algorithm）：Kruskals algorithm(1) 选棱（link）e1 使w(e1)最小； (2) 若已选定 e1 ,e2 ,.,ei ，则从 Ee1 ,e2 ,.,ei中选取 ei+1 使(i) Ge1 ,e2 ,.,ei ei+1 无圈；(ii) w(ei+1)是满足(i)之最小者。(3) 若(2)不能再进行下去时，停止。 否则，回到(2)。 定理2.10 Kruskal算法求出的生成树 = Ge1 ,e2 ,.,en-1 是最优树。证明：反证，假设T* 不是G的最优树。取G的一最优树T。令ek为e1 ,e2 ,.,en-1 中（ 按顺序）第一个不属于T的边，且令T为最优树中使k为最大者。则T+ek中唯一的圈C包含ek ，且C中必含一条边ek T* (不然，C T*，矛盾。）但T = T + ek -ek 也是G的生成树。（因ek不是T + ek的割边（定理2。3），从而T 连通，且其边数=n -1。）又，由于T的子图 Ge1 ,e2 ,.,ek-1 ek 也不含圈，由法算法知w(ek ) w(ek)w(T) w(T)，即T也是G的最优树，且e1 ,e2 ,.,en-1 中第一个不属于T的边的下标 k。这与k的取法相矛盾。 # 实现 先按权的不减顺序将边集重排成a1 ,a2 ,.,ae 。关于算法中无圈性的判定，我们有一简单的办法： 当S=e1 ,e2 ,.,ei 已取定时，对候选边aj GS aj 无圈 aj的两端点在林GS（此处当作生成子图）的不同分支中。从而我们有求最优树的标记法：开始：取a1为候选边； 并将vk标以k， k = 1,2,.,n 。若S=e1 ,e2 ,.,ei 已取定，当候选边aj 的两端点有相同标号时，改取aj+1为 候选边（丢掉aj 永不再考虑）；否则选定ei+1=aj ，并将GS中aj两端点所在的二分支的顶点重新标号，标以两者中的最小者。算法复杂性边排序 O( elog2e ) 比较边两端的标号 e 重新标号 O( n -1)n )故为好算法（ O( n3) ）。附录 （A） Prims algorithm （也是一种贪心算法）T , V ufor all vV do L(v) w(uv) /initializing L(.); V=VVwhile VV do beginfind vertex w s.t. L(w)=min L(v) | v V and denote the associated edge from V to w by eT T e, V V wfor all vV do /updating L(v) from new vertex wL(v) if w(vw) 0 )。 当G为简单图时， k = n -1 G Kn 。称 图G为 k-边连通的