Mengzelev's Blog

图论学习笔记-树

Word count: 1,272 / Reading time: 5 min
2018/10/14 Share

本章可用结论整理

  • 定理4.1:e是图G的桥当且仅当e不在G的任何一个cycle上
  • 定理4.2:图G是树当且仅当G的任意两个顶点只有唯一的path相连
  • 定理4.3:每一棵非简单树都有至少两个端点(end-vertice)
  • 定理4.4:每棵有n个顶点的树都有n-1条边
  • 推论4.6:每棵有k个component的森林都有n-k条边
  • 定理4.7:每一个有n个顶点的连通图至少有n-1条边
  • 定理4.8:有n个顶点、m条边的图G,若满足以下3条性质中的2条:(1)连通 (2)无环 (3)m = n - 1,则G是树
  • 定理4.9:设T是一棵有k个顶点的树。如果图G中最小的度数不小于k-1,那么T与G的某个子图同构
  • 定理4.10:每个连通图都包含了一棵生成树
  • 定理4.15(Tree Formula): 有n个不相同的顶点的树的个数为$n^{n-2}$
  • 定理4.16(Matrix Tree Theorem):

桥(Bridges)

概念

如果$e=uv$是连通图$G$的一条边,且$G-e$不连通,则$e$称为连通图$G$的.

如果$G$是非连通图,那么$e$是G一个部分(component)的桥。

考虑componnet的数目,边$e$是图$G$的桥当且仅当$k(G-e)=k(G)+1$

定理4.1

$e$是图$G$的桥当且仅当$e$不在$G$的任何一个cycle上。

树即无环的连通图
所有的边都是桥。
树也是所有边都是桥的连通图。

双星(double star):包含了恰好两个非端点的树(这两个端点必然相邻)

毛虫树(caterpillar):定点数大于等于3、除去端点后得到的是path的树。
除去端点后得到的path叫作毛虫树的脊椎(spine)
顶点数不小于3的path,star,double star都是毛虫树
端点其实就是毛毛虫的脚脚

森林(Forests):无环图。森林的每个component的都是树。(过于形象
森林不一定要是连通的,但是树必须是。

定理4.2

图$G$是树当且仅当$G$的任意两个顶点只有唯一的path相连

这个证明嘛,只有唯一的path不是和无环是等价的吗(流汗.jpg

定理4.3

每一棵非简单树都有至少两个端点(end-vertice)

证明取了最长路径的两个端点,利用了最长路径上的端点都不与非路径上点相邻的性质,证得最长路径的两个端点都是end-vertice

这条性质非常有用,可以成为对树结构使用数学归纳法的依据,划掉一个端点就会使order-1
使用数学归纳法证明图相关结论的关键在于找到一个end-vertice

定理4.4

每棵有n个顶点的树都有n-1条边

证明使用了基于定理4.3的数学归纳法,很直观

推论4.6

每棵有k个component的森林都有n-k条边

简单的边数计算就能证明

定理4.7

每一个有n个顶点的连通图至少有n-1条边。

证明用到了最小数原理,假设存在一个顶点最少的图少于n-1条边,然后证明此时至少会有一个端点(end vertex),这时就可以把那一个端点去掉得到一个更小的满足条件的图,从而与假设矛盾。

定理4.8

有n个顶点、m条边的图G,若满足以下3条性质中的2条:

  • 连通
  • 无环
  • m = n - 1
    则G是树

证明非常直观,活用了上面的定理

定理4.9

设T是一棵有k个顶点的树。如果图G中最小的度数不小于k-1,那么T与G的某个子图同构

最小生成树问题

实际中存在村庄造路的问题,即造一些路使得所有村庄都连通,并保证造这些路的开销最小
这样的问题可以归结为最小生成树问题,求解一个有权图中权值最小的生成树

Kruskal’s Algorithm

算法描述:先取权最小的两条边,从第三次开始,每次都取不与取过的边构成cycle的、权最小的边,直到取满n-1条边为止。类似于贪心算法。

正确性证明也类似于证明贪心用到的替换法,取最优解中与算法解重叠最大的解,进行替换,导出矛盾。

Prim’s Algorithm

算法描述:先取权最小的一条边,之后每次都选择连接了未连接的点和已连接的点的边中权最小的一条,知道选择了n-1条边为止。类似于动态规划。

证明思路类似于剪切-粘贴法。难以概括……

生成树的个数

书上这部分完全就是在讲故事啊(╯°Д°)╯︵┻━┻

图论证明特点

自己xjb总结的,仅供参考

  • 多用反证法
  • …….我再想想
CATALOG
  1. 1. 本章可用结论整理
  2. 2. 桥(Bridges)
    1. 2.1. 概念
    2. 2.2. 定理4.1
  3. 3.
    1. 3.1. 定理4.2
    2. 3.2. 定理4.3
    3. 3.3. 定理4.4
    4. 3.4. 推论4.6
    5. 3.5. 定理4.7
    6. 3.6. 定理4.8
    7. 3.7. 定理4.9
  4. 4. 最小生成树问题
    1. 4.1. Kruskal’s Algorithm
    2. 4.2. Prim’s Algorithm
  5. 5. 生成树的个数
  6. 6. 图论证明特点