生成树的“变换” 哪条边？ 定理：T与T均是图G的生成树，存在e∈E,但eE,证明 必有e'eEr, 但e'EET,满足：T {e}U{e}和T-{eU{e}均是G的生成树。 证明概要： 这条边！ 设e=u,T-{e}必含两个连通分支，设为T,T,。 T是连通图，T'中有uv-通路，其中必有一边满足其两个端点x,y分别在T,T2中， 设其为e ,显然T-{eU{e}是生成树。 而TU{e}必含唯一回路，且该回路中必定包含e'。将e'从该回路中删去，得到T*=T {eU{e}。显然，T-{e}U{e}是生成树。 问题7：这个定理会被 用于证明最小生成树 算法的正确性，你能 大致推测出怎么用吗？ -T中的通路生成树的“变换” ◼ 定理：T与T'均是图G的生成树，存在eET , 但eET'，证明：必有e'ET' , 但e'ET , 满足：T- {e}⋃{e'}和T'-{e'}⋃{e}均是G的生成树。 ❑ 证明概要： 设e=uv, T-{e}必含两个连通分支，设为T1 , T2。 T‘是连通图，T’中有uv-通路，其中必有一边满足其两个端点x,y分别在T1 , T2中，设其为e ‘ ，显然T-{e}⋃{e’}是生成树。 而T‘⋃{e}必含唯一回路，且该回路中必定包含e’。将e’从该回路中删去，得到T*=T‘- {e’}⋃{e} 。显然， T'-{e'}⋃{e}是生成树。 u e v x e' y T1 T2 T'中的通路 问题7：这个定理会被 用于证明最小生成树 算法的正确性，你能 大致推测出怎么用吗？ 哪条边？ 这条边！