Graph Theory 离散数学第六章图论

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

写这个时的感想
第六章特殊的图

6.1 二部图（偶图）
6.2 欧拉图
6.3 哈密顿图
6.4 平面图

写这个时的感想第二篇了
这几天简直是天天都在考试
马原
大物
选专业
离散
明天就是图论考试
加油
基于老师的ppt和清华大学出版社的《离散数学（第五版）》
第六章特殊的图 6.1 二部图（偶图）

什么是二部图（偶图）
将顶点集分为两个不相交的子集V1和V2（这两个子集被称为是互补顶点子集），使得边集中的任何一条边的两个端点分别属于V1和V2
是二部图的充要条件
当且仅当无向图G中没有长度为奇数的回路
匹配：是边集的子集，且其中任意两条边不相邻的M集合
- 极大匹配：再加入任何一条边便不再是匹配的M
- 最大匹配：边数最多的匹配
  匹配数：最大匹配中的边的条数
- 完美匹配：每个顶点都是饱和点的M
  饱和点：与匹配中的边关联的点（如果不关联就是非饱和点）
- 完备匹配：若V1与V2中较小的一个集合（假定是V1）中的点被最大匹配的边全部关联，那么M就是G中V1到V2的完备匹配
  - 此时，若当V1中点的数量等于V2中点的数量，那么这个完备匹配就是完美匹配
Hall定理（存在完备匹配的充分必要条件）
- 内容：
  设二部图G=，|V1|<=|V2|，
  当且仅当V1中任意k个顶点至少邻接V2中的k个顶点时，
  （加粗部分也被称作为相异性条件）
  G中存在从V1到V2的完备匹配.
- Hall定理的推论：
  内容：设二部图G=，如果存在t>0使得：
  （1）V1中的每个顶点至少关联t条边；
  （2）V2中的每个顶点至少关联t条边；
  （加粗部分被称为t条件）
  则G中存在从V1到V2的完备匹配
应用：选出不兼任的组长

6.2 欧拉图

什么是欧拉图
存在欧拉回路的图叫做欧拉图
- 欧拉回路（通路）：经过有向图/无向图中每条边一次且仅一次并行遍图中每个定点的回路（通路）
存在欧拉回路的充要条件
- 无向图中：当且仅当G是连通图且无奇度定点
- 有向图中：当且仅当G是连通的且每个顶点的入度等于出度
有欧拉通路而无欧拉回路的充要条件
- 无向图中：当且仅当G是连通图且恰好有两个奇度顶点
- 有向图中：
  当且仅当D是连通的；
  且除了两个顶点外，其余顶点入度均等于出度；
  而这两个顶点中，有一个顶点的入度=出度+1（终点），另一个顶点的出度=入度+1（起点）；
本部分内容的应用磁鼓
（以两位数字为前缀码，作为顶点）

6.3 哈密顿图

什么是哈密顿图
- 存在哈密顿回路的图
- 哈密顿回路（通路）：经过图中每个顶点一次且仅一次的回路（通路）
如果一个图是哈密顿图那么：
- 边数>点数
- p（G-V1）<=|V1|
- p（G-V1）<=|V1|+1
无向图G是哈密顿图的充分条件
设G是n（n>=3）阶无向简单图；
G中任何一对不相邻的顶点的度数之和都>=n；
有向图D有哈密顿通路的充分条件
n（n>=2）阶有向图D；
D的基图含有生成子图Kn；
本部分内容的应用
- 竞赛图
  比赛安排流程（任意两个队比赛一次，没有平局，用有向图描述比赛的结果）
- 格雷码
  确定圆盘停止旋转的位置
  （一组n位数，相邻的两个一级最后一个和第一个之间只有一位不同）

6.4 平面图

什么是平面图
能画在平面上使得除顶点处外没有边交叉出现的图
平面嵌入：画出的这种不出现边交叉的图
面
整个平面被G的边划分出的若干个区域
- 外部面/无限面：面积无限的区域
- 内部面/有限面：面积有限的区域
- 边界：包围面R的所有便构成的回路
- 次数：边界的长度
平面图的所有面的次数之和=边数*2
极大平面图
G是一个简单平面图；
G中任意两个不相邻的顶点之间再加一条边，所得图为非平面图时，
那么G是极大平面图
- 判断Gn（n>=3）阶平面图是不是极大平面图：
  G是连通的
  每个面的次数都是3
- 极小平面图
  G是个非平面图；
  G中任意删除一条边，所得图为平面图时；
  那么G是极小非平面图
- 欧拉公式
  - 内容：设G为任意的连通平面图，有：顶点数-边数+面数=2
  - 推广：设G为有p个连通分支的平面图，有：顶点数-边数+面数=连通分支数+1（p>=2）
- 【Graph Theory 离散数学第六章】如果G是连通的平面图且每个面的次数至少为l（l>=3）
  有： m<=l/（l-2）*（n-2）
- 如果G是p（p>=2）个连通分支的平面图且每个面的次数至少为l（l>=3）
  有：m<=l/(l-2)(n-p-1)
收缩：
收缩边：
库拉图斯基定理
- 内容：一个图是平面图，当且仅当他没有可收缩到K5的子图，也没有可收缩到K3,3的子图
是平面图的充分条件
是平面图的必要条件
（面）着色
对偶图：每一个面对应一个点，而原先的图中的边就作为新定义下的点的连接的线
四色定理：任何平面图都是4-可着色的
本部分内容的应用：地图