运筹学讲义 §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 的支撑树的个数：