无向树的性质 定理1 (5)G是连通的,且G中任何边均为桥 (6)G中没有回路,但在任何两个不同的顶点之间加一条新边,在 所得图中得到唯一一个含新边的圈 证明:(5)→(6) 由于G中每条边均为桥,因此,G中无圈 又因为G连通,所以G为树。由(1)→(2)可知:uveV且u≠v, 则u与Ⅴ之间存在唯一的路径r,则rU(uv)为GU(uy)中的圈,显然 该圈是唯一的。9 无向树的性质 定理1. (5) G是连通的, 且G中任何边均为桥 (6) G中没有回路, 但在任何两个不同的顶点之间加一条新边, 在 所得图中得到唯一一个含新边的圈 证明: (5) ⇒ (6) 由于G中每条边均为桥, 因此, G中无圈。 又因为G连通, 所以 G为树。由(1)⇒(2)可知: ∀u,v∈V且u ≠ v, 则u与v之间存在唯一的路径Γ, 则Γ∪(u,v)为G∪(u,v)中的圈, 显然 该圈是唯一的