树
树的基本性质¶
树的叶子数¶
设
证明: 由
又由握手定理得:
由上面两等式得:
森林的分支数¶
具有
证明:
设森林
所以:
图的边数下限¶
每个
证明:
(1) 如果
(2) 如果
对顶点数作数学归纳。
当
设当
当
(2.1) 若
(2.2) 如果
所以,
而当
所以 n 阶连通图 G 至少有 n-1 条边。
所以,树也被称为最小连通图。
任意树
证明:
设
显然,由
树的叶子数下限¶
设
证明:反证法,假设
所以
森林的路分解¶
设
证明: 对
当
设当
在
Info
对图作某种形式的分解,是图论的一个研究对象,它在网络结构分析中具有重要作用。
树的同构子图¶
设
证明: 对
当
假设对
现在设
设
由于
设
树的度序列问题¶
在第一章中,介绍了判定一个非增非负序列是否为简单图的度序列定理。下面介绍一个判定非增非负序列是否为树的度序列的简单方法。
设
; ;
则存在一颗树
证明: 对
当
假设对
首先,序列中至少一个数为 1,否则,序列和大于
所以,
我们从序列中删掉
由归纳假设,存在树
现在,增加结点
树的中心与形心¶
中心¶
- 图的顶点的离心率
; - 图的直径:最大离心率
- 图的半径
; - 图的中心点:离心率等于半径的点
- 图的中心:全体中心点的集合
对树
当
设对
容易知道,删掉
又因
这样,若点
形心¶
设
- 点
的权:树 在 点的分支中边的最大数目称为; - 树
的形心点:树 中权值最小的点 - 树
的形心:全体形心点的集合
每一棵树有一个由一个点或两个邻接的点组成的形心。
生成树¶
生成树的性质¶
每个连通图至少包含一棵生成树
证明:
如果连通图
若连通图
Abstract
定理 1 的证明实际上给出了连通图
推论
若
连通图
生成树的计数¶
凯莱递推计数法¶
凯莱(Cayley 1821-1895): 剑桥大学数学教授,著名代数学家,发表论文数仅次于 Erdos,Euler,Cauchy. 著名成果是 1854 年定义了抽象群,并且得到著名定理:任意一个群都和一个变换群同构。同时,他也是一名出色的律师,作律师 14 年期间,发表 200 多篇数学论文,著名定理也是在该期间发表的。
图
用
证明:对于
凯莱公式的缺点是:
- 计算量很大
- 不能具体指出每棵生成树
关联矩阵计数法¶
n×m 矩阵的一个阶数为
显然,当
时,n×m 矩阵 个主子阵。
设
- 该方法的优点是不仅指出生成树棵数,而且能绘出所有不同生成树;
- 缺点是找所有非奇异主子阵计算量太大!
矩阵树定理¶
该定理是由物理学家克希荷夫提出的。他于 1824 年出生于普鲁士的哥尼斯堡。1845 年因宣布著名的克希荷夫电流电压定律而闻名,1847 年大学毕业时发表了生成树计数文章,给出了矩阵树定理。他的一生主要花在实验物理上。担任过德国柏林数学物理会主席职务
最小生成树¶
Kruskal 算法¶
克鲁斯克尔(Kruskal):1928 年生,一家 3 弟兄都是数学家 1954 年在普林斯顿大学获博士学位,导师是 ErdÖs,他大部分研究工作数学和语言学,主要在贝尔实验室工作。1956 年发表包含克鲁斯克尔算论文,使他名声大振
Abstract
从
算法流程¶
- 选择边
,使得其权值最小; - 若已经选定边
,则从 中选择边 , 使得: 为无圈图 的权值 尽可能小。- 当 (2) 不能进行时,停止。
完备性证明¶
克鲁斯克尔算法得到的任何生成树一定是最小生成树。证明:
设
设
由克鲁斯克尔算法容易知道:
于是令
考虑:
作
设
由克鲁斯克尔算法知道:
所以:
这说明
算法案例¶
- 选一条边
, 使得 尽可能小; - 若边
已经选定,则用下述方法从 中选取边 - (a)
为不相交路之并; - (b)
是满足 (a) 的尽可能小的权。 - 当 (2) 不能继续执行时停止。
Abstract
该方法不能得到一条最小生成路
管梅谷的破圈法¶
在克鲁斯克尔算法基础上,我国著名数学家管梅谷教授于 1975 年提出了最小生成树的破圈法。
从赋权图
不断破圈,直到
Prim 算法¶
Prim 算法是由 Prim 在 1957 年提出的一个著名算法。作者因此而出名。Prim(1921---) 1949 年在普林斯顿大学获博士学位,是 Sandia 公司副总裁。
Abstract
Kruskal 关注边,Prim 关注点
对于连通赋权图
在接下来的边
树图¶
连通图
连通性¶
任何连通图的树图是连通图。
证明:只需证明,对任意
对任意
由树的性质:
该圈中:
作:
此时,
如此这样作下去,可以得到连接
所以,连通图