Graph Theory 离散数学第七章图论

离散数学Ⅰ （图论）期末复习第三篇

写这个时的感想
第七章树

7.1 无向树及生成树
7.2 根树及其应用

写这个时的感想这个就完完整整地一次性写完吧
然后去补充第二篇
最后如果还有精力，我就再写一个算法的（主要是我不想画图）
第七章树 7.1 无向树及生成树

第一部分基础概念（基础中的基础）
- 无向树/树
  不含回路的联通无向图
- 森林
  每个连通分支均是树的非联通无向图
  （也就是很多棵树组成的图）
- 平凡树
  就是平凡图
- 树叶
  树中度数为1的顶点
- 分支点
  度数大于等于2的顶点
是树的充分必要条件
（不分先后）
- G连通且不含回路
- G的每对顶点之间有唯一的一条路径
- G是连通的且边数=顶点数*2
- G中无回路且边数=顶点数*2
- G中无回路，但在任两个不相邻顶点之间增加一条边，就形成唯一的一条初级回路
- G是连通的且每条边都是桥
定理：n阶非平凡的树中至少有两片树叶
证明方法：
假设有k片树叶（度数等于1）
那末
还有n-k个分支点（度数大于等于2）
根据握手定理
以及重要的边数=顶点数*2（树的重要特性）
写出不等式即可
【Graph Theory 离散数学第七章】第二部分概念
- 生成树
  G是连通无向图
  T是G的生成子图并且是树
  那么T就是G的生成树
- 树枝
  G在T中的边
  （叫做T的树枝）
- 弦
  G不在T中的边
  （叫做T的弦）
- 余树
  T的所有弦的集合的导出子图
  （叫做T的余树）
定理：任何无向连通图都有生成树
证明如下：
- 推论：设无向连通图G有m条边，则m>=n+1
  证明如下：
  等于：就是树
  大于：就连一根线出现圈呗
第三部分概念
- 基本回路
  对于每一条弦e，存在唯一的由e和T（G的生成树）的树枝构成的初级回路Ce，Ce就是对应于弦e的基本回路
  性质：连通图中任何一条回路都可表示成它所含弦的基本回路的合并
  - 合并：两个回路的对称差构成的回路
    怎么取对称差：两个集合的并集减去交集的操作。
- 基本回路系统
  所有基本回路的集合
- 基本割集
  T是连通图G的一课生成树，对T的每一条树枝a，存在唯一的由树枝a，其余的边都是弦的割集Sa，称Sa为对应树枝a的基本割集
  性质：连通图中的任一割集都可以表示成它所包含树枝的基本割集的对称差
- 求基本割集的算法（白话解释）
  a是生成树T的树枝
  在T中砍掉a，剩下两个集合T1和T2
  （两个别的生成子树）
  Sa={e|e∈E(G),且e的两个端点分别属于T1和T2}
  //也就是那个e的两个端点属于新生成的生成子树
- 基本割集系统
  所有基本割集的集合
应用：最小生成树问题
最小生成树：权重最小的生成树
避圈法（Kruskal）

7.2 根树及其应用

有向树与根数
- 有向树：一个略去有向边的方向所得无向图为一棵无向树的有向图
- 根数：一棵非平凡的有向树，如果有一个顶点的入度为0，其余顶点的入度均为1，则称此树为根树
- 层数：树根到顶点v的通路长度l（v）
- 树高：顶点的最大层数叫做树高h（T）
家族树与根子树
- 一颗根树可以被看成家族树
  - 父亲&儿子：a邻接到b，则b是a的儿子，a是b的父亲
  - 兄弟：共享父亲
  - 祖先&后代：a可达b，a！=b，则a是b的祖先，b是a的后代
  - 根子树：
    v是根树的一个顶点但不是树根，则v及其所有其后代的导出子图是以v为根的根子树
有序树：将根树同层上的顶点规定次序
根数与有序树的分类
- r叉树：根树的每个分支点的儿子数目<=r
- r叉正则树：根树的每个分支点的儿子数目有且仅有r个
- r叉完全正则树：树叶层数相同的r叉正则树
- r叉有序树：有序的r叉树
- r叉正则有序树：有序的r叉正则树
- r叉完全正则有序树：有序的r叉完全正则树
应用
- 求最优2叉树
  - 最优r叉树：每个顶点都带权，权最小的2叉树
  - Huffman算法
- 求最佳前缀码
  - 前缀码：总之不能互为前后缀（不可翻译）
行遍/周游
- 因访问次序的不同而进行分类
  - 中序行遍法
    左子树->树根->右子树
  - 前序行遍法
    树根->左子树->右子树
  - 后续行遍法
    左子树->右子树->树根
- 行遍的应用（表示算式）
  - 波兰符号法（前缀符号法）
    舍去前序行遍法访问结果中的所有括号的表达
  - 逆波兰符号法（后缀符号法）
    舍去后序行遍法访问结果中的所有括号的表达