第九章树
9.1 无向树及其性质
定义9.1 连通无回路的无向图称为无向树, 或简称树, 常用T表示树(Tree)；平凡图称为平凡树；若无向图G至少有两个连通分支, 每个连通都是树, 则称G为森林(Forest);
在无向图中, 悬挂顶点称为树叶(Leaf);
度数大于或等于2的顶点称为分支点(Node)
无向树有许多性质, 它们是树的充要条件, 因此它们都可看作是树的定义。
定理9.1 设G = <V, E>是n阶m条边的无向图, 则下面各命题是等价的:
(1) G是树
(2) G中任意两个顶点之间存在唯一的路径
(3) G中无回路, 且m = n-1
(4) G是连通的, 且m = n-1
(5) G是连通的, 且G中任何边均为桥
(6) G中没有回路, 但在任何两个不同的顶点之间加一条新边, 在所得图中得到唯一一个含新边的圈
证：(1) ⇒ (2)
由G的连通性和定理14.5的推论可知: ∀u,v∈V, u与v之间存在路径。
若路径不是唯一的, 设Γ1与Γ2都是u到v的路径。
显然必存在由Γ1和Γ2上边构成的回路, 这就与G中无回路矛盾。
(2) ⇒ (3)
先证明: G中无回路。
若G中存在关联某顶点v的环, 则v到v存在长为0和1的两条路经, 这与已知矛盾。
若G中存在长度大于或等于2的圈, 则圈上任何两个顶点之间都存在两条
不同的路径, 这与已知条件矛盾。
下面用归纳法证明: m = n-1。
1) n = 1时, G为平凡图, 结论显然成立。
2) 设n ≤ k(k ≥ 1)时, 结论成立。
3) 当n = k+1时
设e = (u, v)为G中的一条边, 由于G中无回路, 所以, G-e有两个连通分支G1和G2。
设n i和m i分别为G i中的顶点数和边数, 则n i≤ k(i = 1, 2)。
由归纳假设可知: m i = n i-1, 于是, m=m1+m2+1=n1+n2+1-2=n-1。
(3) ⇒ (4)
假设: G不是连通的。
设G由s(s ≥ 2)个连通分支G1, G2, …, G s, G i中均无回路, 因此, G i全为树(i=1..s)。
由(1)⇒(2)⇒(3)可知: m i = n i-1。
于是, m = ∑i=1..s m i = ∑i=1..s n i - s = n - s。
由于s ≥ 2, 这显然与条件“m=n-1”相矛盾。
所以, G是连通的。
(4) ⇒ (5)
证明G中每条边均为桥, ∀e∈E, 均有:
E(G-e) = n-1-1 = n-2。
由“n阶m条边的无向连通图, 则m ≥ n-1”可知: G-e不是连通图, 故e为桥。（5) ⇒ (6)
由于G中每条边均为桥, 因此, G中无圈。
又由于G连通, 所以, G为树。
由(1)⇒(2)可知: ∀u,v∈V且u ≠ v, 则u与v之间存在唯一的路径Γ, 则Γ∪(u,v)为G中的圈, 显然该圈是唯一的。
(6) ⇒ (1)
证明: G是连通的。
∀u, v∈V且u ≠ v, 则(u,v)∪G产生唯一的圈, 显然, 有C - (u,v)为G中u到v 的通路, 故, u ~ v。
由“u和v的任意性”可知: G是连通的。
定理9.2 设T是n阶非平凡的无向树, 则T中至少有两个叶结点。
证：设: T有x个叶结点。
由握手定理和定理9.1可知:
2(n-1) = ∑ d(v i) ≥ x+2(n-x) = 2n-x
由上式可解出: x ≥ 2。
以上定理给出了无向树的主要性质, 利用这些性质和握手定理, 可以画出阶数比较小的所有非同构的无向树。
例9.1 画出6阶所有非同构的无向树。
解：设T i是6阶无向树。
由定理9.1可知: T i的边数m i = 5。
由握手定理可知: ∑j=1..6d Ti(v j) =10, 且δ(T i) ≥ 1, ∆(T i) ≤ 5.
于是, T i的度数列必为以下情况之一:
(1) 1, 1, 1, 1, 1, 5 (2) 1, 1, 1, 1, 2, 4
(3) 1, 1, 1, 1, 3, 3 (4) 1, 1, 1, 2, 2, 3
(5) 1, 1, 2, 2, 2, 2
显然, (4)对应两棵非同构的树, 在一棵树中两个2度顶点相邻, 在另一棵树中不相邻, 其他情况均能画出一棵非同构的树。
(1), (2)和(3)分别对应树T1, T2和T3;
(4)对应树T4和T5;
(5)对应T6。
我们称只有一个分支点, 且分支点的度数为n-1的n (n ≥ 3)阶无向树为星形图, 称其唯一分支点为星心。
上图T1是6阶星形图。
例9.2 7阶无向图有3个叶结点和1个3度顶点, 其余3个顶点的度数均无1和3。试画出满足要求的所有非同构的无向树。
解：设T i为满足要求的无向树, 则边数m i=6。
不妨假设: 结点v1, v2和v3是叶结点, v7是3度结点, v4, v5和v6是待定结点。于是∑j=1..7d(v j) = 12 = 3+3+d(v4)+d(v5)+d(v6)。
由于1 ≤ d(v j) ≤ 6, 且d(v j) ≠ 1和d(v j) ≠ 3可知:
d(v j) = 2 (j = 4, 5, 6)。
于是T i的度数列为: 1, 1, 1, 2, 2, 2, 3。
由度数列可知: T i中有一个3度顶点v7, v7的邻域N(v7)中有3个顶点, 这3个顶点的度数列只能是下列三种之一:
(1, 1, 2), (1, 2, 2), (2, 2, 2)
此度数列只能产生这三棵非同构的7阶无向树, 依次对应右图中的树T1, T2和T3。
9.2 生成树
定义9.2 设树T是无向图G的子图, 则称T为G的树；若树T是G的生成子图, 则称T是G的生成树(Spanning Tree)；设T是G的生成树, ∀e∈E(G), 若
e∈E(T), 则称e为T的树枝, 否则, 称e为T的弦；称导出子图G[E(G)-E(T)]为余树, 记作T;
注意: T的余树没有什么特点。在下图中, 实边图为该图的一棵生成树T, 虚线部分是构成T的余树。它不连通, 但含回路。
定理9.3 无向图G具有生成树, 当且仅当G是连通图。
二叉树的基本性质证：
1) 必要性
由“生成树的定义”可知: 图G是连通图。
2) 充分性。
若G中无回路, G为自己的生成树。
若G中含圈, 任取一圈, 任意删除圈上的一条边, 若还有圈, 再删除圈上的一条边, 直到剩下的图无圈为止。
显然, 最后所得的图G’无圈、连通且为G的生成子图。
所以, 图G’就是G的生成树。
推论1 设G为n阶m条边的无向连通图, 则m ≥ n-1。
证：由定理9.3可知: G有生成树。
设T为G的一棵生成树, 则m = |E(G)| ≥ |E(T)| = n-1。
推论2 设G是n阶m条边的无向连通图, T为G的生成树, 则T的余树中含有m-n+1条边。
（可由推论1获得。）
推论3 设T是连通图G的一棵生成树, T为T的余树, C为G中任意一个圈, 则E(T)∩E(C) ≠φ。
证：若E(T)∩E(C) = φ, 则E(C) ⊆ E(T), 这说明C为T中圈。
这显然与“T是树”相矛盾。
定理9.4 设T为无向连通图G中一棵生成树, e为T的任意一条弦, 则T∪e 中一定存在圈, 且该圈含弦e, 其余边均在T中。
证：设: e = (u, v)。
由定理9.1可知: 在T中, u和v之间存在唯一的路径Γ(u,v), 则Γ(u,v)∪e就是一个满足要求圈。
由定理9.4, 可以得出下面的定义。
定义9.3 设T是n阶m条边的无向连通图G的一棵生成树, e’1, e’2, …,
e’m-n+1为T的弦,
C r为T添加弦e’r产生的圈, 该圈含弦e’r, 其余边均在树T中, 称C r为G对应T的弦e’r的基本回路或基本圈(-n+1)；称{ C1, C2, …, C m-n+1 }为G 对应T的基本回路系统, 称m-n+1为G的圈秩, 记作ξ(G) [读: Sai]。
在右图中, 生成树T的弦分别为e6, e7, e8, e10和e11。
假设这些弦所对应的基本回路分别为C1, C2, C3, C4和C5。
从弦开始, 按顺时针顺序写出的回路分别为:
C1 = e6e4e5, C2 = e7e2e1, C3 = e8e9e2e1
C4 = e10e3e5e2, C5 = e11e3e5e2e9
因此, 该图的圈秩为5, 基本回路系统为
{ C1, C2, C3, C4, C5 }。
由此不难看出: 无向连通图G的圈秩与生成树的选取无关, 但不同生成树所对应的基本回路系统可能不同。
定理9.5 设T是连通图G的一棵生成树, e为T的树枝, 则G中存在只含树枝e, 其余边都是弦的割集, 且不同的树枝对应的不同割集。
证：由定理9.1可知: e是T的桥。
假设: T-e有两个连通分支T1和T2。
令S e = { e | e∈E(G), e = (v i, v j), v i∈V(T1)和v j∈V(T2) }。
由构造可知: S e为G的割集, e∈S e且S e中除e外都是弦, 所以, 边集S e即为所求。
不同树枝对应的割集显然也是不同的。
定义9.4 设T是n阶连通图G的一棵生成树, e’1, e’2, …, e’n-1为T的树枝, S i 是G的只含树枝e’i的割集, 则称S i为G的对应生成树T由树枝e’i生成的基本割集(-1)称{ S1, S2, …, S n-1 }为G对应T的基本割集系统
称n-1为G的割集秩, 记作η(G)[读: eitә]

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。