图论 王智慧 复旦大学计算机学院
图论 王智慧 复旦大学计算机学院
树 无向树及其性质 ·生成树 根树及其应用
2 树 • 无向树及其性质 • 生成树 • 根树及其应用
无向树的定义 定义1 连通无回路的无向图称为无向树,或简称树,常用T表示树 平凡图称为平凡树;若无向图G至少有两个连通分支,每个连通 都是树,则称G为森林 在无向树中,悬挂顶点称为树叶;度数大于或等于2的顶点 称为分支点
3 无向树的定义 定义1. 连通无回路的无向图称为无向树, 或简称树, 常用T表示树 平凡图称为平凡树; 若无向图G至少有两个连通分支, 每个连通 都是树, 则称G为森林. 在无向树中, 悬挂顶点称为树叶; 度数大于或等于2的顶点 称为分支点
无向树的性质 无向树有许多性质,其中一些是树的充要条件,可看作是树的 等价定义 定理1.设G=是n阶m条边的无向图,则下面各命题是等价的: (1)G是树 (2)G中任意两个顶点之间存在唯一的路径 (3)G中无回路,且m=n-1 (4)G是连通的,且m=n-1 (5)G是连通的,且G中任何边均为桥 (6)G中没有回路,但在任何两个不同的顶点之间加一条新边,在 所得图中得到唯一的一个含新边的圈
4 无向树的性质 (1) G是树 (2) G中任意两个顶点之间存在唯一的路径 (3) G中无回路, 且m = n-1 (4) G是连通的, 且m = n-1 (5) G是连通的, 且G中任何边均为桥 (6) G中没有回路, 但在任何两个不同的顶点之间加一条新边, 在 所得图中得到唯一的一个含新边的圈 无向树有许多性质, 其中一些是树的充要条件, 可看作是树的 等价定义。 定理1. 设G = 是n阶m条边的无向图, 则下面各命题是等价的:
无向树的性质 定理1 (1)G是树;(2)G中任意两个顶点之间存在唯一的路径 证明:(1)→(2) 由树的定义可知u,v∈G(V),u与V之间存在路径。若路径 不是唯一的,设∏1与2都是u到v的路径,那么必存在由1和2上边 构成的回路,这就与G中无回路矛盾 5
5 无向树的性质 证明: (1) ⇒ (2). 由树的定义可知 ∀u,v∈G(V), u与v之间存在路径。若路径 不是唯一的, 设Γ1与Γ2都是u到v的路径, 那么必存在由Γ1和Γ2上边 构成的回路, 这就与G中无回路矛盾。 定理1. (1) G是树; (2) G中任意两个顶点之间存在唯一的路径
无向树的性质 定理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是连通的