无向树的性质 定理1 (2)G中任意两个顶点之间存在唯一的路径;(3)G中无回路,且m=n-1 证明:(2)→(3) 先证明G中无回路。若G中存在关联某顶点V的环,则v到存在长为0 和1的两条路径,这与已知矛盾。若G中存在长度大于或等于2的圈,则圈上 任何两个顶点之间都存在两条不同的路径,这也与已知条件矛盾。 下面用归纳法证明:m=n-1。 当n=1时,G为平凡图,结论显然成立 假设n≤k(k≥1)时,结论成立 当n=k+1时,设e={u,v)为G中的一条边,由于G中无回路,所以,G-e 有两个连通分支G1和G2。设n和m分别为G中的顶点数和边数,则n1≤k(i =1,2)。由归纳假设可知,m=n1,于是m=m1+m2+1=n1+n2+1-2=n-1
6 无向树的性质 定理1. (2) G中任意两个顶点之间存在唯一的路径;(3) G中无回路, 且m = n-1 证明: (2) ⇒ (3) 先证明 G中无回路。若G中存在关联某顶点v的环, 则v到v存在长为0 和1的两条路径, 这与已知矛盾。若G中存在长度大于或等于2的圈, 则圈上 任何两个顶点之间都存在两条不同的路径, 这也与已知条件矛盾。 下面用归纳法证明: m = n-1。 当 n = 1时, G为平凡图, 结论显然成立。 假设n ≤ k(k ≥ 1)时, 结论成立。 当n = k+1时, 设e = (u, v)为G中的一条边, 由于G中无回路, 所以, G-e 有两个连通分支G1和G2。设ni和mi分别为Gi中的顶点数和边数, 则ni ≤ k (i = 1, 2)。由归纳假设可知, mi = ni-1, 于是 m=m1+m2+1=n1+n2+1-2=n-1
无向树的性质 定理1 (3)G中无回路,且m=n-1;(4)G是连通的,且m=n-1 证明:(3)→(4) 假设G不是连通的。不失一般性,设G包含S(S≥2个连通分 支G1G2,…,Gs,其中G(=1.s为n阶m条边且无回路,因此G1 全为树(i=1.s)。 由(1)→(2)→(3)可知,对于每个G有m1=n1-1。于是,m E=1.m=E=1.n4-s=n-s。由于s≥2,这显然与条件“m=n1” 相矛盾。所以,G是连通的
7 无向树的性质 证明: (3) ⇒ (4) 假设G不是连通的。不失一般性, 设G包含s(s ≥ 2)个连通分 支G1, G2, …, Gs, 其中Gi(i=1..s)为ni阶mi条边且无回路, 因此, Gi 全为树(i=1..s)。 由(1)⇒(2)⇒(3)可知, 对于每个Gi, 有mi = ni-1。于是, m = Σi=1..smi = Σi=1..sni - s = n - s。由于s ≥ 2, 这显然与条件“m=n-1” 相矛盾。所以, G是连通的。 定理1. (3) G中无回路, 且m = n-1; (4) G是连通的, 且m = n-1
无向树的性质 定理1 (4)G是连通的,且m=n-1;(5)G是连通的,且G中任何边均为桥 证明:(4)→(5) ve∈E,从G中删除e后,均有E(G-e)=n-1-1=n-2,vG-e)=m 由“n阶m条边的无向连通图,则m≥n-1”,可知Ge不是连通图,故e 为桥,也即G中每条边均为桥 可通过对n做数学归纳法证明:“n阶m条边的无向连通图,则m
8 无向树的性质 定理1. (4) G是连通的, 且m = n-1; (5) G是连通的, 且G中任何边均为桥 证明: (4) ⇒ (5) ∀e∈E, 从G中删除e后, 均有E(G-e) = n-1-1 = n-2, V(G-e)=m. 由“n阶m条边的无向连通图, 则m ≥ n-1”, 可知 G-e不是连通图, 故e 为桥, 也即G中每条边均为桥. 注: 可通过对n做数学归纳法证明: “n阶m条边的无向连通图, 则m ≥ n-1
无向树的性质 定理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)中的圈, 显然 该圈是唯一的
无向树的性质 定理1 (6)G中没有回路,但在任何两个不同的顶点之间加一条新边,在 所得图中得到唯一一个含新边的圈 (1)G是树 证明:(6)→(1).只要证明G是连通的。 vu,veV且u≠v,则(U,)UG产生唯一的圈,显然,有C-({u,v)为G中 u到v的通路,故,U~V。由u和v的任意性,所以G是连通的。 10
10 无向树的性质 定理1. (6) G中没有回路, 但在任何两个不同的顶点之间加一条新边, 在 所得图中得到唯一一个含新边的圈 (1) G是树 证明: (6) ⇒ (1). 只要证明G是连通的。 ∀u, v∈V且u ≠ v, 则(u,v)∪G产生唯一的圈, 显然, 有C - (u,v)为G中 u到v的通路, 故, u ~ v。由u和v的任意性, 所以G是连通的