运筹学讲义 y P 若P与Q无公共边,则P+Q恰为T的一个圈,与T是树矛盾;否则,彐e=xy∈E(P)\E(Q) 显然,(P+Q)-e连通,故(P+Q)-e中彐一条(x,y)-路W.于是,W+e是T的一个圈,与T是 树矛盾 ←设T的任两顶点之间恰有唯一一条路相连,则T连通.下证T 无圈.(反证法)假设T中有一个圈C=v1v2…Vxv4V1,则vvk 与C-v1vk是连结顶点v1,v的两条不同的路,与唯一性矛盾. k-1 (1)分(5):→设T是树,则T连通.下证去掉T的任一条边后即不连通 (反证法)假设彐e=∈E(T),使得T-e仍连 通,则u,v之间有一条路P相连.于是,P+e是T 的一个圈,与T是树矛盾. ←设T连通,且去掉任一条边后即不连通,则仅需证T无圈. (反证法)假设T中有一个圈C=v1V2…vh=vv1,则易见 ve∈E(C),T-e仍连通,矛盾 1)(6):→设T是树,则T无圈.下证在T的任两顶点之间添加一条边即得一个圈. Va,∈(T),由T是树知,T连通,∴l,v之 v间有一条路P相连.在T中添加边m,则P+m 即为T+n的一个圈运 筹 学 讲 义 6 若 P 与 Q 无公共边，则 P + Q 恰为 T 的一个圈，与 T 是树矛盾；否则，  e = xy E(P) \ E(Q) . 显然， (P + Q) − e 连通，故 (P + Q) − e 中  一条 (x, y) −路 W .于是， W + e 是 T 的一个圈，与 T 是 树矛盾.  设 T 的任两顶点之间恰有唯一一条路相连，则 T 连通.下证 T 无圈.（反证法）假设 T 中有一个圈 1 2 1 1 C v v v v v =  k− k ，则 k v v1 与 k C v v − 1 是连结顶点 k v ,v 1 的两条不同的路，与唯一性矛盾. （1）  （5）：  设 T 是树，则 T 连通.下证去掉 T 的任一条边后即不连通. （反证法）假设 e = uv  E(T) ，使得 T −e 仍连 通，则 u, v 之间有一条路 P 相连.于是， P + e 是 T 的一个圈，与 T 是树矛盾.  设 T 连通，且去掉任一条边后即不连通，则仅需证 T 无圈. （反证法）假设 T 中有一个圈 1 2 1 1 C v v v v v =  k− k ，则易见 e  E(C) ，T −e 仍连通，矛盾. （1）  （6）：  设 T 是树，则 T 无圈.下证在 T 的任两顶点之间添加一条边即得一个圈. u, v V (T) ，由 T 是树知，T 连通，  u, v 之 间有一条路 P 相连.在 T 中添加边 uv ，则 P +uv 即为 T +uv 的一个圈