无向树的定义及性质
树
:
连通无回图
无向树
?
树
(tree):
连通无回图
,
常用
T
表示树
?
树叶
(leaf):
树中
1
度顶点
?
分支点
:
树中
2
度以上顶点
?
平凡树
:
平凡图
(
无树叶
,
无分支点
)
?
森林
(forest):
无回图
?
森林的每个连通分支都是树
树的等价定义
?
定理
9.1
:
设
G=<V,E>
是
n
阶
m
边无向图
,
则
(1) G
是树
(
连通无回
)
(2) G
中任何
2
顶点之间有唯一路径
(3) G
无圈 等价
m=n-1
(4) G
连通 等价
m=n-1
(5) G
极小连通
:
连通 等价
所有边是桥
(6) G
极大无回
:
无圈 等价
增加任何新
边产生唯
一圈
定理
9.2
?
非平凡树至少有
2
个树叶
无向树的计数
: t
n
?
t
n
: n(>=
1)
阶非同构无向树的个数
?
t
n
的
生成函数
(generating function):
t(x) = t
1
x + t
2
x^
2
+ t
3
x ^
3
+…+ t
n
x ^
n
+…
?
Otter
公式
:
t(x) = r(x) - ( r(x)^
2
- r(x^
2
) ) / 2
r(x) = r
1
x + r
2
x ^
2
+ r
3
x ^
3
+…+ r
n
x ^
n
+…
星
: S
n
=K
1,n-1
生成树
?
生成树
: T包含于
G 并
V(T)=V(G) 并
T
是树
?
树枝
(tree edge): e属于
E(T),
n-1
条
?
弦
(chord): e属于
E(G)-E(T), m-n+1
条
?
余树
(): G[E(G)-E(T)] = T（T顶上有一条横线，实在打不出）
定理
9.3
?
无向图
G
连通
?
G
有生成树
定理
9.4
?
设
G
是连通图
, T
是
G
的生成树
, e
是
T
的弦
,
则
T并集
e
中存在由弦
e
和其他树枝组成的圈
,
并且
不同的弦对应不同的圈
生成树的计数
: t
(G)
? t
(G)
:
标定图
G
的生成树的个数
?
T
1不等于
T
2
: E(T
1
)不等于
E(T
2
)
?
G-e:
删除
(deletion)
?
G\e:
收缩
(contraction)