运筹学讲义 显然,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 ，且 eC .又由 G 无环知， e 不是环.  e  C ，且 e   e .令 T = T + e −e  ，则 T  显然也是 G 的一个支撑树，且 T   T ， 矛盾.▌ 例 8 求证：（1）若图 G 连通，且 eE ，则 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 ，且 eC ，这与 e 是 G 的割边矛盾.▍ 注：（逆否命题） e 不属于 G 的某一个支撑树  e 不是 G 的割边； e 属于 G 的某一个支撑树  e 不是 G 的环. 支撑树问题：求连通图 G 的一个支撑树. 算法 1：破圈法 理论依据：Th2 充分性的证明. 基本思想：在保持连通性的前提下，逐次破开图 G 的所有圈（去掉圈的任一条边即可），直到无 圈时为止. 算法 2：避圈法 理论依据：Th1(2). 基本思想：在保持无圈性的前提下，从图 G 的某一顶点开始，逐次生长边，直到连通（所有顶点 都被生长到）时为止. 例 8 求图 G 的支撑树： 解：（1）破圈法： （2）避圈法：