离散数学大概（四）

1. 树
   连通无回路的无向图称为无向树，或树。每个连通分支都是树的无向图称为森林。平凡图称为平凡树。在无向树中，悬挂顶点（度数为1的顶点）称为树叶，度数大于或等于2的顶点称为分支点
2. 设G是n阶m条边的无向图

• G中任意两个顶点之间存在唯一的路径
• G中无回路且m=n-1
• G是连通的且任何边均为桥
• G中没有回路，但在任何两个不同的顶点之间加一条新边后所得图中有唯一的一个含有新边的圈
• 设T是n阶非平凡的无向树，则T中至少有两片树叶

3. 割点
   在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，但是去掉顶点集合的真子集中的顶点，图的连通分量不变，就称这个点集为点割集。
   如果点割集只含有一个顶点，则称该顶点为割点
4. 割集
   割集S是连通图G的边的集合，如果把S中的边都去掉，则图G的连通分量会增多，但是如果去掉S的真子集中的边，则图的连通分量不变。割集其实是一种极小集合。
   如果割集只有一条边，则称该边为割边或桥
5. 生成树

• 如果无向图G的生成子图T是树，则称T是G的生成树。G的在T中的边称为T的树枝，不在T中的边称为T的弦，称T的所有弦的导出子图为T的余树
• 无向图G有生成树当且仅当G是连通图
• 数据分析中的单链聚类
  同一子类中的数据尽可能接近，而不同子类中的数据尽可能远离。可采用最小生成树Kruskal算法解决这个问题，在最小生成树建立过程中不断计算当前的连通分支个数，直到恰好有k个连通分支时算法停止，得到的k个连通分支就是所求聚类的k个子类

6. 有向树
   若有向图的基图是无向树，则称这个有向图是有向树。
   一个顶点的入度为0，其余顶点的入度为1的有向树称为根树。入度为0的顶点称为树根，入读为1出度为0的顶点称为树叶，入度为1出度不为0的顶点称为内点，内点和树根统称为分支点。从树根到任意顶点v的路径的长度（路径的边数）称为v的层数，所有顶点的最大层数称为树高
7. 有序树

• 设T为根树，若将T中层次相同的顶点都标定次序，则称T为有序树
• 若T的每个分支点至多有r个儿子，则称T为r叉树；又若T是有序的，则称为r叉有序树
• 若T的每个分支点恰好有r个儿子，则称T为r叉正则树；又若T是有序的，则称它为r叉正则有序树

8. 最优二叉树-权最小的2叉树-哈夫曼树

• 设A是一个符号串集合，若A中任意两个符号串都互不为前缀，则称A为前缀码
• 通信时采用非等长二进制码表示要传输的符号，可节省二进制位数。用各个符号出现的频率作为权的最优2叉树产生的前缀码所用的二进制位数最少

9. 波兰符号法
   利用2叉正则树可以表示四则运算的算式，然后根据不同的遍历方法会得到不同的算法。用2叉正则树表示算式的方法如下：参加运算的数都放在树叶上，然后按照运算的顺序依次将运算符放在分支点上，每个分支点表示一个运算，同时也表示这个运算的结果，它以它的两个运算对象为儿子，并规定被除数、被减数放在左边。

• 中序遍历该2叉正则树会还原算式
• 前序遍历：从右到左每个运算符对它后面紧邻的两个数进行运算。这种算法由于运算符在它的两个运算对象之前，所以称为前缀符号法或波兰符号法
• 后序遍历：从左到右每个运算符对它前面紧邻的两个数进行运算。这种算法由于运算符在它的两个运算对象之后，所有称为后缀符号法或逆波兰符号法

10. 平面图
    如果能将无向图G画在平面上使得除顶点处外无边相交，则称G为可平面图，简称平面图。画出的无边相交的图称为G的平面嵌入。无平面嵌入的图称为非平面图。

• K5和完全二部图K3,3都是非平面图
• 平面图的子图都是平面图，非平面图的母图都是非平面图
• 若G是平面图，则在G中加平行边或环后所得图还是平面图
• 给定平面图G的平面嵌入，G的边将平面分成若干个区域，每个区域都称为G的一个面，其中有一个面的面积无限，称为无限面或外部面，其余面的面积有限，称为有限面或内部面。包围每个面的所有边组成的回路称为该面的边界，边界的长度称为该面的次数
• 平面图所有面的次数之和等于边数的两倍
• 设G是简单平面图，若在G的任意两个不相邻的顶点之间加一条边，所得图为非平面图，则称G为极大平面图
• 设G是n（n≥3）阶简单连通的平面图，G为极大平面图当且仅当G的每个面的次数均为3

11. 欧拉公式

• 欧拉研究多面体时发现多面体的顶点数减去棱数加上面数等于2
• 设连通平面图G的顶点数n，边数m，面数r，则n-m+r=2
• 推广：对于有k个连通分支的平面图，有n-m+r=k+1

12. 匹配

• 设无向简单图G=<V,E>，E* 包含于E，若E* 中任何两条边均不相邻，则称E* 为G的边独立集，也称为G的匹配。G的边数最多的匹配称为最大匹配，最大匹配中的边数称为边独立数或匹配数
• 与匹配边相关联的顶点为饱和点，不与匹配边相关联的顶点为非饱和点
• 若G中每个点都是饱和点，则称匹配M为G的完美匹配

13. 二部图中的匹配
    设G=<V1,V2,E>为二部图，|V1|≤|V2|，M为G的一个匹配且 |M|=|V1|，称M为V1到V2的完备匹配

• 二部图的完备匹配是最大匹配，但是最大匹配不一定是完备匹配。当|v1|=|v2|时，完备匹配就是完美匹配

14. （Hall定理）二部图有完备匹配的充要条件，也称相异性条件
    设二部图G=<V1,V2,E>，其中|V1|≤|V2|，则G中存在V1到V2的完备匹配当且仅当V1中任意k个顶点至少与V2中k个顶点相邻
15. （t条件定理）二部图有完备匹配的充分条件
    设二部图G=<V1,V2,E>，如果存在正整数 t，使得V1中的每个顶点至少关联 t 条边，而V2中的每个顶点至多关联 t 条边，则G中存在V1到V2的完备匹配
16. 点着色
    设无向图G无环，对G的每个顶点涂一种颜色，使相邻的顶点涂不同的颜色，称为图G的一种点着色。若能用k种颜色给G的顶点着色，则称G是k-可着色的。若G是k-可着色的，但不是(k-1)-可着色的，则称G的色数为k.
17. 地图着色
    连通无桥平面图的平面嵌入及其所有的面称为地图，地图的面称为‘国家’。若两个国家的边界至少有一条公共边，则称这两个国家是相邻的。
    对地图G的每个国家涂上一种颜色，使相邻的国家涂不同的颜色，称为对地图G的面着色。
    地图G是k-可面着色的当且仅当它的对偶图是k-可着色的。
    四色定理：任何平面图都是4-可着色的。
18. 边着色
    对图G的每条边着一种颜色，使相邻的边着不同的颜色，称为对图G的边着色。若G是k-可边着色的，但不是(k-1)-可边着色的，则称G的边色数为k

• 简单图的边色数只可能取两个值：最大度 或者 最大度+1
• 二部图的边色数等于最大度