CSGNAK的博客

图论2——树

Word count: 1.8kReading time: 7 min
2021/10/12 Share

2.1 树的基本概念

定义 2.1. 连通无圈图称为树，用TT表示。树中度数为1的顶点称为树叶，度数大于1的顶点称为分支点，边称为树枝。每个连通片都是树的非连通图称为森林。孤立点称为平凡树。

截屏2021-10-12 下午4.16.01

定理 2.1. 设G=(V(G),E(G))G=(V(G),E(G))是简单无向图，则以下命题等价：

  • GG是树。
  • GG的任意两个顶点之间有且仅有一条轨道。
  • GG不含图，且ε(G)=ν(G)−1\varepsilon(G)=\nu(G)-1。
  • GG是连通图，且ε(G)=ν(G)−1\varepsilon(G)=\nu(G)-1。
  • GG是连通图，且山区任意一条边都不连通。
  • GG不含圈，且任意添加一条边后恰好含一个圈。

定理 2.2. 任一平凡树TT至少有两片树叶。

  • 利用Euler定理证明。

定义 2.2. 设图G=(V,E)G=(V,E)是连通图，任取v∈Vv\in V，称l(v)=max⁡{dist(u,v∣u∈V}l(v)=\max\{dist(u,v|u\in V\}是顶点vv的离心率，称r(G)=min⁡{l(v)∣v∈V}r(G)=\min\{l(v)|v\in V\}是图GG的半径。离心率恰好等于半径(即l(v)=r(G)l(v)=r(G))的顶点vv，称为GG的一个中心点。GG中全体中心点的集合称为GG的中心。

截屏2021-10-12 下午4.39.42

2.2 生成树

定义 2.3. 如果图GG的生成子图TT是树，则称TT是GG的一棵生成树；如果TT是森林，称它为GG的生成森林。生成树的边称为树枝，图GG中非生成树的边称为弦。TT相对于GG的补图TGcT^c_G称为GG的余树。TGcT^c_G是GG的生成子图，其边集合由GG中不在TT上的边组成。

定理 2.3. 每个连通图都有生成树。

  • 推论 2.1. 若GG是连通图，则ε(G)≥ν(G)−1\varepsilon(G)\geq\nu(G)-1。
  • 推论 2.2. GG是连通图的充分必要条件是GG有生成树。

定理 2.4. (Cayley)设G是连通图，e=uv∈E(G)e=uv\in E(G)且不是环，则τ(G)=τ(G−e)+τ(G⋅e)。\tau(G)=\tau(G-e)+\tau(G·e)。其中，G⋅eG·e是GG中收缩掉边ee后得到的图(收缩图)。

定理 2.5. τ(Kn)=nn−2\tau(K_n)=n^{n-2}

2.3 最小生成树

定义 2.4. 给定连通边权图G=(V(G),E(G),ω)G=(V(G),E(G),\omega)，其中，ω:E(G)→R+\omega:E(G)\to R^+为边权函数，GG的生成树TT的权定义为W(T)=∑e∈E(T)ω(e)W(T)=\sum_{e\in E(T)}\omega(e)，权最小的生成树称为GG的最小生成树。

算法 2.1. KruskalKruskal算法。**输入：**加权图G=(V(G),E(G),ω),ν=∣V(G)∣G=(V(G),E(G),\omega),\nu=|V(G)|。输出：GG的一棵生成树的边子集{e1,e2,...,eν−1}\{e_1,e_2,...,e_{\nu-1}\}。

  • 从E(G)E(G)中选权最小的边e1e_1；
  • 若已经选定边{e1,e2,...,ei}\{e_1,e_2,...,e_i\}，则从E(G)−E(G)-{e1,e2,...,ei}\{e_1,e_2,...,e_i\}中选出边ei+1e_{i+1}，使得(i)(i)边导出子图[{e1,e2,...,ei}][\{e_1,e_2,...,e_i\}]不含圈；(ii)(ii)在满足(i)(i)的前提下，ω(ei+1)=min⁡e∈E(G)−{e1,e2,...,ei}ω(e)\omega(e_{i+1})=\min_{e\in E(G)-\{e_1,e_2,...,e_i\}}\omega(e)。
  • 反复执行第二步直到选出eν−1e_{\nu-1}为止。
截屏2021-10-12 下午5.25.36

定理 2.6. 由KruskalKruskal算法得到的生成子图T∗=(V(G),{e1,e2,...,ei})T^*=(V(G),\{e_1,e_2,...,e_i\})是最小生成树。

算法 2.2. PrimPrim算法。输入：边权图G=(V(G),E(G),ω),ν=∣V(G)∣G=(V(G),E(G),\omega),\nu=|V(G)|。输出：GG的一棵生成树的边子集E′E'。

  • 从V(G)V(G)中任意选取一个顶点ss，令V′=s，E′=∅V'={s}，E'=\empty；
  • 在(V′,V′‾)(V',\overline{V'})中选择一条最小的边uvuv，其中u∈V′,v∈V′‾u\in V',v\in \overline{V'}。令V′=V′∪{v},E′=E′∪{uv}V'=V'\cup\{v\},E'=E'\cup\{uv\}；
  • 反复执行第二步直到∣V′∣=ν|V'|=\nu或∣E′∣=ν−1|E'|=\nu-1为止。

定理 2.7. 由PrimPrim算法得到的图T∗=(V′,E′)T^*=(V',E')是最小生成树。

截屏2021-10-12 下午5.43.54

**破圈法：**区别于避圈法(KruskalKruskal算法和Prim$算法)。参考习题16。

截屏2021-10-12 下午5.45.27

2.4 二叉树及其应用

定义 2.5. 有根树是指定一个顶点作为根，并且每条边的方向都离开根的有向树。设TT是一棵非平凡的有根树，任给vi,vj∈V(T)v_i,v_j\in V(T)，若(vi,vj)∈E(T)(v_i,v_j)\in E(T)，则称viv_i为vjv_j的父亲，vjv_j是viv_i的儿子；同父之子称为兄弟；若从viv_i到vjv_j有有向轨道，viv_i为vjv_j的祖先，vjv_j是viv_i的后代。

定义 2.6. 在有根树中仅有一个顶点入度为0，其余顶点的入度均为1。有根树TT中入度为0的顶点就是根，入度为1出度为0的顶点称为树叶，入度为1出度不为0的顶点称为内点，内点和根统称为分支点。从根到TT的任一顶点vv到距离称为vv的深度L(v)L(v)，深度的最大值称为树高h(T)h(T)。

  • 入度：顶点的入边条数。出度：顶点的出边条数。

定义 2.7. 设TT是一棵有根树，若每个顶点的孩子都从左到右规定了次序，则称TT是有序树。

定义 2.8. 设TT是一棵有根树，

  • 若TT的每个分支点至多有rr个儿子，则称TT是rr叉树；
  • 若TT的每个分支点都恰好有rr个儿子，则称TT是rr叉正则树；
  • 若TT是rr叉正则树且每个树叶的深度都是树高，则称TT是rr叉完全正则树；
  • 若TT是rr叉树且为有序树，则称TT是有序rr叉树；
  • 若TT是rr叉正则树且为有序树，则称TT是有序rr叉正则树；
  • 若TT是rr叉完全正则树且为有序树，则称TT是有序rr叉完全正则树。

定理 2.8. 二叉树有以下性质：

  • 第ii层的顶点数最多是2i2^i；
  • 深度为hh的二叉树最多有2h+1−12^{h+1}-1个顶点；
  • 设二叉树出度为2的顶点数为n2n_2，树叶数为n0n_0，则有n0=n2+1n_0=n_2+1；
  • 包含nn个顶点的二叉树的高度至少为log⁡(n+1)−1\log(n+1)-1。
CATALOG
  1. 1. 2.1 树的基本概念
  2. 2. 2.2 生成树
  3. 3. 2.3 最小生成树
  4. 4. 2.4 二叉树及其应用
Total : 9
2021
数据结构 心得 计算系统概论 大二上
数据结构