Skip to content

树的基本性质

树的叶子数

T(n,m) 树,T 中有 ni 个度为 i,(1ik) 的点,且有 ni=n ,则有:n1=2+n3+2n4++(k2)nk

证明: 由 m=n1 得:

m=(n1+n2++np)1

又由握手定理得:

2m=n+2n2++knk

由上面两等式得:

n1=2+n3+2n4++(k2)nk

森林的分支数

具有 k 个分支的森林有 nk 条边。


证明:

设森林 Gk 个分支为 Ti(1ik) ,对每个分支,使用定理 3 得

m(Ti)=ni1(ni=|V(Ti)|)

所以:

m(G)=i=1km(Ti)=nk

图的边数下限

每个 n 阶连通图的边数至少为 n1.

证明:

(1) 如果 n 阶连通图 G 没有一度顶点,那么由握手定理有:

m(G)=12vV(G)d(v)n

(2) 如果 G 有一度顶点:

对顶点数作数学归纳。

n=1 时,结论显然

设当 n=k 时,结论成立。

n=k+1 时,设 uG 的一度顶点,则 Gu 为具有 k 个顶点的连通图

(2.1) 若 Gu 有一度顶点,则由归纳假设,其边数至少 k1 ,于是 G 的边数至少有 k 条;

(2.2) 如果 Gu 没有一度顶点,由握手定理有:

m(Gu)=12vV(Gu)d(v)k

所以,G 至少有 k+1 条边。

而当 G 是树时,边数恰为 n1 .

所以 n 阶连通图 G 至少有 n-1 条边。

所以,树也被称为最小连通图。

任意树 T 的两个不邻接顶点之间添加一条边后,可以得到唯一圈


证明:

uv 是树 T 的任意两个不邻接顶点,由定理 2 知:有唯一路 P 连接 uv ;于是 P{uv} 是一圈。

显然,由 P 的唯一性也就决定了 P{uv}的唯一性。

树的叶子数下限

G 是树且 Δk ,则 G 至少有 k 个一度顶点(叶子顶点)


证明:反证法,假设 G 有至多 k1 个叶子顶点

2m(G)=vV(G)d(v)k1+k+2(nk)=2n1>2n2

所以 m(G)>n1 ,与 G 是树矛盾!

森林的路分解

G 是森林且恰有 2k奇度顶点,则在 G 中有 k 条边不重合的路 P1,P2,,Pk 使得:

E(G)=E(P1)E(P2)E(Pk)

证明: 对 k 作数学归纳。

k=1 时,G 只有两个奇数度顶点,此时,容易证明,G 是一条路;

设当 k=t 时,结论成立。令 k=t+1

G 中一个分支中取两个一度项点 uv ,令 P 是连接该两个项点的唯一路,则 GP 是有 2t 个奇数顶点的森林,由归纳假设,它可以分解 t 条边不重合的路之并,所以 G 可以分解为 t+1 条边不重合的路之并。

Info

对图作某种形式的分解,是图论的一个研究对象,它在网络结构分析中具有重要作用。

树的同构子图

Tk 阶树。若图 G 满足 δk1 ,则 T 同构于 G 的某个子图。

证明: 对 k 作数学归纳

k=1 时,结论显然。

假设对 k1,(k3) 的每颗树 T ,以及最小度至少为 k2 的每个图 HT1 同构于 H 的某个子图 F

现在设 Tk 阶树,且图 G 满足 δk1 ,证明 T 同构于 G 的某个子图:

uT 的树叶,vu 的邻接顶点。则 Tuk1 阶树。

由于 δ(G)k1>k2 ,由归纳假设,Tu 同构于 G 的某个子图 F

树的同构子图证明

v 是与 Tv 相对应的 F 中的点,由于 dG(v1)k1 ,所以 vG 中一定有相异于 F 中的邻点 w ,作 F{u1w} ,则该子图和 T 同构。

树的度序列问题

在第一章中,介绍了判定一个非增非负序列是否为简单图的度序列定理。下面介绍一个判定非增非负序列是否为树的度序列的简单方法。

S={d1,d2,,dn}n 个正整数序列,它们满足:

  • d1d2dn
  • di=2(n1)

则存在一颗树 T ,其度序列为 S


证明: 对 n 作数学归纳。

n=1,2 时,结论显然。

假设对 n=k 时结论成立。设 n=k+1,

首先,序列中至少一个数为 1,否则,序列和大于 2k ,与条件相矛盾!

所以,dk+1=1

我们从序列中删掉 d1dk+1 ,增加数 d=di1 放在它应该在的位置。得到序列 S ,该序列含 k 个数,序列和为 2(k1)

由归纳假设,存在树 T ,它的度序列为 Si

现在,增加结点 v ,把它和 T1 中点 d 相连得到树 T 为所求

树的中心与形心

中心

  1. 图的顶点的离心率 e(v)=max{d(u,v)|uV(G)}
  2. 图的直径最大离心率
  3. 图的半径 r(G)=min{e(v)|vV(G)}
  4. 图的中心点离心率等于半径的点
  5. 图的中心:全体中心点的集合

对树 T 的阶数 n 作归纳证明。

n=1,2 时,结论显然成立

设对 n<k,(k3) 的树结论成立,设 Tk 阶树

容易知道,删掉 T 的所有叶,得到的树 T ,的每个点的离心率比它们在 T 中离心率减少 1

又因 T 的叶不能是中心点,所以 T 的中心点在 T1

这样,若点 u 的离心率在 T 中最小,则在 T1 中依然最小,即说明 T 的中心点是 T1 的中心点,反之亦然。

形心

u 是树 T 的任意一个顶点,树 T 在顶点 u 的分支是指包含 u 作为一个叶点的极大子树,其分支数为顶点 u 的度数;

  1. u:树 Tu 点的分支中边的最大数目称为;
  2. T形心点:树 T权值最小的点
  3. T形心:全体形心点的集合

每一棵树有一个由一个点两个邻接的点组成的形心。

生成树

生成树的性质

每个连通图至少包含一棵生成树


证明:

如果连通图 G 是树,则其本身是一棵生成树;

若连通图 G 中有圈 C ,则去掉 C 中一条边后得到的图仍然是连通的,这样不断去掉 G 中圈,最后得到一个 G 的无圈连通子图 T ,它为 G 的一棵生成树。

Abstract

定理 1 的证明实际上给出了连通图 G 的生成树的求法,该方法称为破圈法

推论

G(n,m) 连通图,则 mn1

连通图 G 的生成树一般不唯一⚠

生成树的计数

凯莱递推计数法

凯莱(Cayley 1821-1895): 剑桥大学数学教授,著名代数学家,发表论文数仅次于 Erdos,Euler,Cauchy. 著名成果是 1854 年定义了抽象群,并且得到著名定理:任意一个群都和一个变换群同构。同时,他也是一名出色的律师,作律师 14 年期间,发表 200 多篇数学论文,著名定理也是在该期间发表的。

G 的边 e 称为被收缩,是指删掉 e 后,把 e 的两个端点重合,如此得到的图记为G\cdote

τ(G) 表示 G 的生成树颗数。

τ(G)=τ(Ge)+τ(Ge)

证明:对于 G 的一条边 e 来说,G 的生成树中包含边 e 的棵数为 Ge ,而不包含 e 的棵数为 Ge

凯莱公式的缺点是:

  • 计算量很大
  • 不能具体指出每棵生成树

关联矩阵计数法

n×m 矩阵的一个阶数为 min{n,m} 的子方阵,称为它的一个主子阵;主子阵的行列式称为主子行列式

显然,当 n<m 时,n×m 矩阵 Cmn 个主子阵。

Am 是连通图 G 的基本关联矩阵的主子阵,则 Am 非奇异的充分必要条件是相应于 Am 的列的那些边构成 G 的一棵生成树。

  • 该方法的优点是不仅指出生成树棵数,而且能绘出所有不同生成树;
  • 缺点是找所有非奇异主子阵计算量太大!

矩阵树定理

该定理是由物理学家克希荷夫提出的。他于 1824 年出生于普鲁士的哥尼斯堡。1845 年因宣布著名的克希荷夫电流电压定律而闻名,1847 年大学毕业时发表了生成树计数文章,给出了矩阵树定理。他的一生主要花在实验物理上。担任过德国柏林数学物理会主席职务

G 的生成树棵数为拉普拉斯矩阵 L 的任意一个元素的代数余子式。

最小生成树

Kruskal 算法

克鲁斯克尔(Kruskal):1928 年生,一家 3 弟兄都是数学家 1954 年在普林斯顿大学获博士学位,导师是 ErdÖs,他大部分研究工作数学和语言学,主要在贝尔实验室工作。1956 年发表包含克鲁斯克尔算论文,使他名声大振

Abstract

G 中的最小边开始,进行避圈式扩张。

算法流程
  1. 选择边 e1 ,使得其权值最小;
  2. 若已经选定边 e1,e2,,ek ,则从 E{e1,e2,,ek} 中选择边 ek+1 , 使得:
  3. [e1,e2,,ek+1] 为无圈图
  4. ek+1 的权值 w(ek+1) 尽可能小。
  5. 当 (2) 不能进行时,停止。
完备性证明

克鲁斯克尔算法得到的任何生成树一定是最小生成树。证明:

G 是一个 n 阶连通赋权图,用 T=G[{e1,e2,,en1}](导出子图)表示由克鲁斯克尔算法得到的一棵生成树,我们证明:它是最小生成树

TG 的一棵最小生成树。若 TT.

由克鲁斯克尔算法容易知道:TT.

于是令 f(T)=k 表示 T 中的边 ei 不在 T 中的最小 i 值。即可令 T=G[{e1,e2,,ek1,ek,,en1}](导出子图)

考虑:Tek , 则由树的性质,它必然为 G 中圈 C .

T1=Teke , 容易知道:T1 还为 G 的一棵生成树。

e 是圈 C 的在 T 中,但不在 T 中的边。

由克鲁斯克尔算法知道:w(e)w(ek) .

所以:w(T)w(T1) .

这说明 T1 是最小树,但这与 f(T) 的选取假设矛盾!所以:T=T

算法案例

  1. 选一条边 e1 , 使得 w(e1) 尽可能小;
  2. 若边 e1,e2,,ei 已经选定,则用下述方法从 E{e1,e2,,ei} 中选取边 ei+1
  3. (a) G[{e1,e2,,ei+1}] 为不相交路之并;
  4. (b) w(ei+1) 是满足 (a) 的尽可能小的权。
  5. 当 (2) 不能继续执行时停止。

Abstract

该方法不能得到一条最小生成路

管梅谷的破圈法

在克鲁斯克尔算法基础上,我国著名数学家管梅谷教授于 1975 年提出了最小生成树的破圈法。

从赋权图 G 的任意圈开始,去掉该圈中权值最大的一条边,称为破圈。

不断破圈,直到 G 中没有圈为止,最后剩下的 G 的子图为 G 的最小生成树

Prim 算法

Prim 算法是由 Prim 在 1957 年提出的一个著名算法。作者因此而出名。Prim(1921---) 1949 年在普林斯顿大学获博士学位,是 Sandia 公司副总裁。

Abstract

Kruskal 关注边,Prim 关注点

对于连通赋权图 G 的任意一个顶点 u ,选择与点 u 关联的且权值最小的边作为最小生成树的第一条边 e1 ;

在接下来的边 e2,e3,,en1, 在与一条已经选取的边只有一个公共端点的的所有边中,选取权值最小的边。

树图

连通图 G 的树图是指这样的图,它的顶点是 G 的生成树 T1,T2,,TτTiTj 相连当且仅当它们恰有 n2 条公共边。

连通性

任何连通图的树图是连通图。


证明:只需证明,对任意 TiTj ,在树图中存在连接它们的路即可!

对任意 TiTj , 设 e1,e2,,ek (k<n2) 是它们的公共边。

由树的性质:ek+1E(Ti) , 但 ek+1E(Tj) , 使得:Tj+ek+1 有唯一圈。

该圈中: ek+1E(Tj) , 但 ek+1E(Ti)

作: Ti+1=Tiek+1+ek+1 ,则 TiTi+1n2 条边相同,于是,它们邻接。

此时,Ti+1Tjk+1 条边相同。

如此这样作下去,可以得到连接 TiTj 的一条路为:Ti,Ti+1,,Tj

所以,连通图 G 的树图是连通的。