运筹学讲义 §2.2.2最小树与森林 支撑(生成)树( spanning tree): a spanning subgraph of a graph G which is itself a tree. 支撑树T 例1画出下列各图的所有不同构的支撑树: (3) (1)K4 (2) 解:(1) K E4的不同构的支撑树 Q2Q3994990612q3994961020399496 (3)易见,图的悬挂点和悬挂边均恒在其支撑树上.∴找所给图的非同构的支撑树等价于找下图 的支撑树
运 筹 学 讲 义 1 §2.2.2 最小树与森林 支撑（生成）树（spanning tree）：a spanning subgraph of a graph G which is itself a tree. 例 1 画出下列各图的所有不同构的支撑树： （1） K4 ； （2） （3） 解：（1） （2） （3）易见，图的悬挂点和悬挂边均恒在其支撑树上. 找所给图的非同构的支撑树等价于找下图 的支撑树：
运筹学讲义 此图共有两个非同构的支撑树 故所给图的非同构的支撑树为 注:图的悬挂点和悬挂边均恒在其支撑树上 树枝( branch):G在T中的边;弦:G不在T中的边;余树:G的弦导出子图 注:(1)图的支撑树可能不存在,如含有孤立点的图(即不连通图);即使存在(何种图才存在 支撑树?见Th2),也可能不唯一,但边数均为v-1 (2)图的支撑树是其极小连通支撑子图( minimal connected spanning subgraph),即在图的 所有连通支撑子图中,树含有的边数最少 图的支撑树是其极大无圈支撑子图( minimal connected spanning subgraph),即在图的所有无 圈支撑子图中,树含有的边数最多 (3)若T是图G的一个支撑树,则T的边数为v-1,G的不在T上的边数为 v-1)=E-v+1
运 筹 学 讲 义 2 此图共有两个非同构的支撑树： 故所给图的非同构的支撑树为 ▌ 注：图的悬挂点和悬挂边均恒在其支撑树上. 树枝（branch）： G 在 T 中的边；弦： G 不在 T 中的边；余树： G 的弦导出子图. 注：（1）图的支撑树可能不存在，如含有孤立点的图（即不连通图）；即使存在（何种图才存在 支撑树？见 Th2），也可能不唯一，但边数均为 −1. （2）图的支撑树是其极小连通支撑子图（minimal connected spanning subgraph），即在图的 所有连通支撑子图中，树含有的边数最少. 图的支撑树是其极大无圈支撑子图（minimal connected spanning subgraph），即在图的所有无 圈支撑子图中，树含有的边数最多. （ 3 ） 若 T 是 图 G 的一个支撑树，则 T 的边数为 −1 ， G 的不在 T 上的边数为 − ( −1) = − +1
运筹学讲义 例2在完全图K中去掉多少条边才能得到(支撑)树? 解:(Kn)-(T)=C2-(v-1)= v(V-1) (v-1)= (v-1)(V-2) Th1图G有支撑树◇G连通 证明:→设图G有支撑树T,则vu,v∈(G),∵V(G)=V(T),∴由§2.2.2Thl(4)知, ,v之间恰有唯一一条路相连,即,v连通.故由u,v选取的任意性知,G连通 另证:∵图G的支撑树是其极小连通支撑子图! ←设G连通,若G无圈,则G本身即为其支撑树;否则,可在保持连通性的前提下,逐次破开G 的所有圈(去掉圈的任一条边即可),即得其一个支撑树■ Corollary任一非平凡无环连通图均至少含有两个非割点的顶点 证明:Th1+ Lemma1+树的定义的注(1).■ 例3(1)求证:若G是有v个顶点的连通图,则E≥v-1:(2)当G是何种连通图时,E=v-1? 证明:∵G连通,∴由Th2知,G有支撑树T.于是,(O)≥E(T)=v(T)-1=v(G)-1 (2)当连通图G无圈,即G是树时,E=V-1.■ 注:(逆否命题)若E<ψ-1,则图G不连通. 例4求证:若n个城市中的任何两个均可通电话(直通或转通),则此通信网络中必存在至少n-1 条直通线路 证明:以n个城市为顶点,顶点之间有边相连当且仅当城市之间有直通线路,作图G 于是,此问题分→证明n个顶点的连通图G必有一个含有n-1条边的支撑树.由Thl得证■ 例5求证:若T是连通图G的支撑树,则ve∈E(O)\E(T),T+e中含有唯一一个圈 证明:∵T是G的极大无圈支撑子图,∴T+e中必含有一个圈C,且e∈C.令e=v,则由 §2.2.1Th1(6)知,T中存在唯一一条(,v)-路,从而C是唯一的■ 例6求证:任一连通图G中都至少含有E-v+1个不同的圈 证明:由G连通及Th2知,G中至少存在一个支撑树T.由例5知,Ve∈E(G)\E(T),T+e 中含有G的唯一一个圈.易见,当选取不同的e时,T+e中含有的这样的圈也不同.又由支撑树的定 义的注(3)知,|E(G)\E(T)|=E-(v-1)=E-v+1.故G中至少含有E-v+1个不同的圈■ 例7求证:若无环图G恰有一个支撑树T,则G=T 证明:∵:T是G的支撑树,∴G连通,且V(G)=V().为证G=T,只需证E(G)=E(T)
运 筹 学 讲 义 3 例 2 在完全图 K 中去掉多少条边才能得到（支撑）树？ 解： 2 ( 1)( 2) ( 1) 2 ( 1) ( ) ( ) ( 1) 2 − − − − = − − = − − = Kn T C .▌ Th1 图 G 有支撑树 G 连通. 证明： 设图 G 有支撑树 T ，则 u,v V(G) ，V(G) = V(T) , 由§2.2.2 Th1（4）知， u, v 之间恰有唯一一条路相连，即 u, v 连通.故由 u, v 选取的任意性知， G 连通. 另证： 图 G 的支撑树是其极小连通支撑子图！ 设 G 连通,若 G 无圈，则 G 本身即为其支撑树；否则，可在保持连通性的前提下，逐次破开 G 的所有圈（去掉圈的任一条边即可），即得其一个支撑树.▌ Corollary 任一非平凡无环连通图均至少含有两个非割点的顶点. 证明：Th1 + Lemma1 + 树的定义的注（1）.▌ 例 3(1)求证：若 G 是有 个顶点的连通图，则 −1 ；(2)当 G 是何种连通图时， = −1 ？ 证明： G 连通， 由 Th2 知， G 有支撑树 T .于是， (G) (T) = (T) −1 = (G) −1. (2)当连通图 G 无圈，即 G 是树时， = −1.▌ 注：（逆否命题）若 −1 ，则图 G 不连通. 例 4 求证：若 n 个城市中的任何两个均可通电话（直通或转通），则此通信网络中必存在至少 n −1 条直通线路. 证明：以 n 个城市为顶点，顶点之间有边相连当且仅当城市之间有直通线路，作图 G . 于是，此问题 证明 n 个顶点的连通图 G 必有一个含有 n −1 条边的支撑树.由 Th1 得证.▌ 例 5 求证：若 T 是连通图 G 的支撑树，则 e E(G) \ E(T) ，T + e 中含有唯一一个圈. 证明： T 是 G 的极大无圈支撑子图， T + e 中必含有一个圈 C ，且 eC .令 e = uv ，则由 §2.2.1 Th1（6）知， T 中存在唯一一条 (u,v) − 路，从而 C 是唯一的.▌ 例 6 求证：任一连通图 G 中都至少含有 − +1 个不同的圈. 证明：由 G 连通及 Th2 知， G 中至少存在一个支撑树 T .由例 5 知， e E(G) \ E(T) ，T + e 中含有 G 的唯一一个圈.易见，当选取不同的 e 时， T + e 中含有的这样的圈也不同.又由支撑树的定 义的注（3）知， | E(G) \ E(T) |= − ( −1) = − +1.故 G 中至少含有 − +1 个不同的圈.▌ 例 7 求证：若无环图 G 恰有一个支撑树 T ，则 G = T . 证明： T 是 G 的支撑树， G 连通，且 V(G) = V(T) .为证 G = T ，只需证 E(G) = E(T)
运筹学讲义 显然,E(T)sE(G).下证E(G)cE(T).为此,只需证ve∈E(G),e∈E(T) (反证法)假设egE(T),则由例5知,T+e含有唯一一个圈C,且e∈C.又由G无环知, e不是环.∴彐e'∈C,且e'≠e.令T'=T+e-!',则T'显然也是G的一个支撑树,且T≠T, 矛盾■ 例8求证:(1)若图G连通,且e∈E,则巳属于G的每一个支撑树◇e是G的割边. (2)e不属于G的任一个支撑树分e是G的环 证明:此处只证(1) →(反证法)假设e不是G的割边,则e含于G的某一圈C中.于是,在利用破圈法构造G的 支撑树时,e既可破掉亦可不破掉.如此,e有可能属于G的某一支撑树,而不属于G 支撑树 这与e属于G的每一个支撑树矛盾 (反证法)假设T1,T2都是G的支撑树,但e∈E(T)\E(T2),则T2+e中至少含有G的一 个圈C,且e∈C,这与e是G的割边矛盾 注:(逆否命题)e不属于G的某一个支撑树e不是G的割边;e属于G的某一个支撑树 不是G的环 支撑树问题:求连通图G的一个支撑树 算法1:破圈法 理论依据:Th2充分性的证明 基本思想:在保持连通性的前提下,逐次破开图G的所有圈(去掉圈的任一条边即可),直到无 圈时为止 算法2:避圈法 理论依据:Th1(2) 基本思想:在保持无圈性的前提下,从图G的某一顶点开始,逐次生长边,直到连通(所有顶点 都被生长到)时为止 例8求图G的支撑树: G 解:(1)破圈法: (2)避圈法
运 筹 学 讲 义 4 显然， E(T) E(G).下证 E(G) E(T).为此，只需证 e E(G) ，e E(T) . （反证法）假设 e E(T) ，则由例 5 知， T + e 含有唯一一个圈 C ，且 eC .又由 G 无环知， e 不是环. e C ，且 e e .令 T = T + e −e ，则 T 显然也是 G 的一个支撑树，且 T T ， 矛盾.▌ 例 8 求证：（1）若图 G 连通，且 eE ，则 e 属于 G 的每一个支撑树 e 是 G 的割边. （2） e 不属于 G 的任一个支撑树 e 是 G 的环. 证明：此处只证（1）. （反证法）假设 e 不是 G 的割边，则 e 含于 G 的某一圈 C 中.于是，在利用破圈法构造 G 的 支撑树时， e 既可破掉亦可不破掉.如此， e 有可能属于 G 的某一支撑树，而不属于 G 的另一支撑树， 这与 e 属于 G 的每一个支撑树矛盾. （反证法）假设 1 2 T ,T 都是 G 的支撑树，但 ( ) \ ( ) E T1 E T2 e ，则 T + e 2 中至少含有 G 的一 个圈 C ，且 eC ，这与 e 是 G 的割边矛盾.▍ 注：（逆否命题） e 不属于 G 的某一个支撑树 e 不是 G 的割边； e 属于 G 的某一个支撑树 e 不是 G 的环. 支撑树问题：求连通图 G 的一个支撑树. 算法 1：破圈法 理论依据：Th2 充分性的证明. 基本思想：在保持连通性的前提下，逐次破开图 G 的所有圈（去掉圈的任一条边即可），直到无 圈时为止. 算法 2：避圈法 理论依据：Th1(2). 基本思想：在保持无圈性的前提下，从图 G 的某一顶点开始，逐次生长边，直到连通（所有顶点 都被生长到）时为止. 例 8 求图 G 的支撑树： 解：（1）破圈法： （2）避圈法：
运筹学讲义 支撑树的个数 图G的支撑树的个数:r(G) 图的收缩( contract):G·e( e is deleted from G and two endpoints of e are identified) Lν It is clear that if e is a link of G, then v(G e)=v(G)-1, E( e)=EG) O(G·e)=O(G) Cayley's Theorem If e is a link of G, thenr(G)=r(G-e)+rGe Proof:显然,G的任一支撑树或含有e,或不含有e 方面,G的任一不含有巳的支撑树必定也是G-e的支撑树,∴G的不含有e的支撑树的个数 为r(G-e);另一方面,G的任一含有e的支撑树T显然唯一对应G·e的支撑树r·e,∴G的含有 e的支撑树的个数为r(G·e)综上,有r(G)=r(G-e)+r(G·e).l iE: Cayley's Theorem provides a recursive (ise y) method of calculating the number of panning trees in a graph 例求图G的支撑树的个数:
运 筹 学 讲 义 5 ▌ 支撑树的个数 图 G 的支撑树的个数： (G) . 图的收缩（contract）： G e （ e is deleted from G and two endpoints of e are identified） It is clear that if e is a link of G ，then (G e) = (G) −1， (G e) = (G) −1， (G e) = (G) . Cayley’s Theorem If e is a link of G ，then (G) = (G − e) + (G e) . Proof：显然， G 的任一支撑树或含有 e ，或不含有 e . 一方面， G 的任一不含有 e 的支撑树必定也是 G − e 的支撑树， G 的不含有 e 的支撑树的个数 为 (G − e) ；另一方面， G 的任一含有 e 的支撑树 T 显然唯一对应 G e 的支撑树 T e ， G 的含有 e 的支撑树的个数为 (G e) .综上，有 (G) = (G − e) + (G e) .▍ 注：Cayley’s Theorem provides a recursive（递归） method of calculating the number of spanning trees in a graph. 例 求图 G 的支撑树的个数：
运筹学讲义 G △。 +○ =1+1+1+1+1+1+1+1=8 注:(1)为方便书写,可用图本身来符号化的表示图的支撑树的个数.(2)递归地计算到每一图 都是树或带有环的“树”时,即可停止 几个结论:
运 筹 学 讲 义 6 ▍ 注：（1）为方便书写，可用图本身来符号化的表示图的支撑树的个数.（2）递归地计算到每一图 都是树或带有环的“树”时，即可停止. 几个结论：
运筹学讲义 r(Kn)=n2:轮Wn(≥3)的支撑树的个数为r(n)=-2+3-523+√5 2 最小树 Ex (weight ) endow one edge one figure (e. g length, distance, time, capac flow cost, etc.) 赋权图( a weighted graph): a graph each edge of which is endowed a weight. 最小(权支撑)树(MST, minimum weight spanning tree): a certain spanning tree with mum weight among all spanning trees of a weighted graph. (Here, the weight of a tree is defined as sum of weights of all edges of the tree 注:连通的赋权图必有最小树,但可能不唯 最小(权支撑)树问题(MSTP, minimum weight spanning tree problem): find a minimum weight spanning tree of a weighted graph? 最小树问题是一种重要的组合最优化( combinatorial optimization)问题. 问题的背景( background):城市输电线路的架设问题 今欲将η个城市用电缆连结起来建立一个输电网络.问应如何架设输电线路,才能把n个城市都 连结起来,且造价最省(即所用的电缆的总长度最短)? 若以n个城市为顶点,以城市之间可能的架设线路为边,构造一个图G,则易见上述问题即为求 图G的一个最小树的问题. 最小树算法的理论依据 树T是赋权图G的最小树分Va∈E(G)\E(T),有w(a)≥max{w(e)} 故T必由那些权较小而不形成圈的边构成 最小树算法: 1.破圈法:1967年, Rosenstiehl;管梅谷 基本思想:在保持连通性的前提下,逐次去掉图G的所有圈中的权最大的边,直到无圈时为止 2.避圈法( Kruscal算法,Prim算法):1956年,美国,J.B. Kruscal 基本思想:在保持无圈性的前提下,从图G的某一顶点开始,逐次生长权最小的边,直到连通(所 有顶点都被生长到)时为止 破圈法和避圈法都属于“贪心( greedy)”算法 例9分别利用破圈法和避圈法求图G的最小树: 7
运 筹 学 讲 义 7 2 ( ) − = n Kn n ；轮 W (n 3) n 的支撑树的个数为 n n Wn ) 2 3 5 ) ( 2 3 5 ( ) 2 ( + + − = − + . 最小树 权（weight）：endow one edge one figure（e.g.length， distance，time，，capacity，flow， cost，etc.） 赋权图（a weighted graph）：a graph each edge of which is endowed a weight. 最小（权支撑）树（MST，minimum weight spanning tree）：a certain spanning tree with minimum weight among all spanning trees of a weighted graph. （Here，the weight of a tree is defined as sum of weights of all edges of the tree） 注：连通的赋权图必有最小树，但可能不唯一. 最小（权支撑）树问题（MSTP，minimum weight spanning tree problem）：find a minimum weight spanning tree of a weighted graph？ 最小树问题是一种重要的组合最优化（combinatorial optimization）问题. 问题的背景（background）：城市输电线路的架设问题 今欲将 n 个城市用电缆连结起来建立一个输电网络．问应如何架设输电线路，才能把 n 个城市都 连结起来，且造价最省（即所用的电缆的总长度最短）？ 若以 n 个城市为顶点，以城市之间可能．．的架设线路为边，构造一个图 G ，则易见上述问题即为求 图 G 的一个最小树的问题． 最小树算法的理论依据： 树 T 是赋权图 G 的最小树 a E(G) \ E(T) ，有 ( ) max{ ( )} ( ) w a w e eE T ． 故 T 必由那些权较小而不形成圈的边构成． 最小树算法： 1．破圈法：1967 年，Rosenstiehl；管梅谷 基本思想：在保持连通性的前提下，逐次去掉图 G 的所有圈中的权最大的边，直到无圈时为止. 2．避圈法（Kruscal 算法，Prim 算法）：1956 年，美国，J．B．Kruscal 基本思想：在保持无圈性的前提下，从图 G 的某一顶点开始，逐次生长权最小的边，直到连通（所 有顶点都被生长到）时为止. 破圈法和避圈法都属于“贪心（greedy）”算法. 例 9 分别利用破圈法和避圈法求图 G 的最小树：
运筹学讲义 G 解:(1)破圈法 (2)避圈法 注:类似地,可考虑最大树问题及其算法 E 1分别利用破圈法和避圈法求图G的最小树: 10 2平面xO上有9个点:A(0,15),B(5,20),C(1624),D(20,20),E(33,25) F(2311)G(35,7),H(250),(10,3).定义两点i,j间的距离为w(1,)=x-x|+1y2-y·问 如何连结各点,才能使所有点都连通,且总距离最短? 森林( forest): an acyclic graph
运 筹 学 讲 义 8 解：（1）破圈法： （2）避圈法： ▌ 注：类似地，可考虑最大树问题及其算法． E.g.: 1 分别利用破圈法和避圈法求图 G 的最小树： 2 平 面 xOy 上 有 9 个点： A(0,15) ， B(5,20) ， C(16,24) ， D(20,20) ， E(33,25) ， F(23,11) G(35,7), H(25,0)，I(10,3) ．定义两点 i, j 间的距离为 ( , ) | | | | i j i j w i j = x − x + y − y ．问 如何连结各点，才能使所有点都连通，且总距离最短？ 森林（forest）：an acyclic graph．
运筹学讲义 如 显然,若T是树,则v∈V(T),T-ν必是森林(∵T-v的各连通分支显然是树!) Lema1若图G无孤立点,且E≤v-(o≥1),则G至少有一个悬挂点 证明:(反证法)假设G无悬挂点,则由G无孤立点知,yv∈V,d(v)≥2,i=1,2,…,v 于是,2E=∑()2∑2=2→E≥v,与E≤v-0≤v-1矛盾■ 注:注意Lema1与§2.2.2 Lemma2的异同 性质:(1)F是森林台F的每一个连通分支都是树;树是连通分支数O=1的森林 (2)F是森林分E=v-(≥1) 证明:(1)∵森林的每一个连通分支都连通且无圈 (2)→设F是森林,其各连通分支为T1,T2…,T。,则由(1)知,T1,T2,…,T。都是树,故 6(F)=∑=(7)=∑()-1=∑v(T)-=v(F) ←设E=v-0,下证F无圈.W.L.0.G.设F无孤立点 (对v作数归法)当v=1时,O=1,E=V-0=0,无圈 设当=k-1时,无圈性成立,则当v=k时,由Lema知,F至少有一个悬挂点v 显然,(F-v)=k-1.∴由归纳假设知,F-V无圈.当然,F也无圈 故综上知,F无圈,从而F是森林■ 注:由(1)知,树是连通分支数O=1的森林;再由(2)知,树的边数为E=v-O=V-1 Th a graph F is a forest if and only if every edge of F
运 筹 学 讲 义 9 如 显然，若 T 是树，则 v V(T) ，T −v 必是森林（ T −v 的各连通分支显然是树！） Lemma1 若图 G 无孤立点，且 − ( 1) ，则 G 至少有一个悬挂点． 证明：（反证法）假设 G 无悬挂点，则由 G 无孤立点知， vi V,d(vi ) 2,i =1,2, , . 于是， = = = = 2 ( ) 2 2 1 1 p i p i i d v ，与 − −1 矛盾.▌ 注：注意 Lemma1 与§2.2.2 Lemma 2 的异同. 性质：（1） F 是森林 F 的每一个连通分支都是树；树是连通分支数 =1 的森林． （2） F 是森林 = − ( 1) ． 证明：（1） 森林的每一个连通分支都连通且无圈． （2） 设 F 是森林，其各连通分支为 T T T , , , 1 2 ，则由（1）知， T T T , , , 1 2 都是树，故 = = − = − = − = = = ( ) ( ) [ ( ) 1] ( ) ( ) 1 1 1 F T T T F i i i i i i . 设 = − ，下证 F 无圈.W.L.O.G.设 F 无孤立点. （对 作数归法）当 =1 时， =1， = − = 0 ，无圈； 设当 = k −1 时，无圈性成立，则当 = k 时，由 Lemma1 知， F 至少有一个悬挂点 v . 显然， (F − v) = k −1. 由归纳假设知， F − v 无圈.当然， F 也无圈. 故综上知， F 无圈，从而 F 是森林.▌ 注：由（1）知，树是连通分支数 =1 的森林；再由（2）知，树的边数为 = − = −1. Th A graph F is a forest if and only if every edge of F is a cut edge
运筹学讲义 Proof:(: refer to 02-02(1)Th2 for reference) F is a forests every connected component of F is a trees every edge of f is a cut edge. 支撑(生成)森林( spanning forest): F a spanning subgraph of a graph g which is itself a forest(本身是森林的支撑子图) 注:(1)图的支撑森林必定存在,且可能不唯一,但边数均为q=p- (2)图的支撑森林是其极大森林( maximal forest) F是图G的极大森林◇→F匚G是森林,且ⅤFcHG,H不是森林. (3)若F是图G的一个支撑森林,则F的边数为E=v-0,G的不在F上的边数为 (4)若F是图G的一个支撑森林,则ⅤG的一个连通分支H,F∩H是H的支撑树 例10求证:任一图G中都至少含有E-v+O个不同的圈,O≥1. 证明:(1)若O=1,则由例6得证:(2)若O≥2,则设G的各连通分支为G1G2,…G。,则 由例6知,G2中含有的不同的圈的个数至少为sG)-V(G)+1,i=1,2,…,O.于是,G中含有的 不同的圈的个数至少为∑[(G)-v(G)+1∑6(G)-∑v(G)+O=E-v+O
运 筹 学 讲 义 10 Proof:(:refer to 02-02(1) Th2 for reference). F is a forest every connected component of F is a tree every edge of F is a cut edge.▌ 支撑（生成）森林（spanning forest）： F a spanning subgraph of a graph G which is itself a forest（本身是森林的支撑子图）. 注：（1）图的支撑森林必定存在，且可能不唯一，但边数均为 q = p − . （2）图的支撑森林是其极大森林（maximal forest）. F 是图 G 的极大森林 F G 是森林，且 F H G ， H 不是森林. （3）若 F 是图 G 的一个支撑森林，则 F 的边数为 = − ， G 的不在 F 上的边数为 − ( −) = − + . （4）若 F 是图 G 的一个支撑森林，则 G 的一个连通分支 H ， F H 是 H 的支撑树. 例 10 求证：任一图 G 中都至少含有 − + 个不同的圈， 1. 证明：(1)若 =1 ，则由例 6 得证；(2)若 2 ，则设 G 的各连通分支为 G G G , , , 1 2 ，则 由例 6 知， Gi 中含有的不同的圈的个数至少为 (Gi ) −(Gi ) +1，i = 1,2, , .于是， G 中含有的 不同的圈的个数至少为 − + = − + = − + =1 =1 =1 [ ( ) ( ) 1] ( ) ( ) i i i i i Gi Gi G G .▌