当前位置: 代码迷 >> 综合 >> 树 离散数学
  详细解决方案

树 离散数学

热度:99   发布时间:2023-12-05 13:06:01.0
无向树的定义及性质
: 连通无回图
无向树
? (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)
  相关解决方案