本文共 1792 字，大约阅读时间需要 5 分钟。
离散数学Ⅰ（图论）期末复习第二篇
第二篇感想
这几天简直是天天都在考试，马原、大物、选专业、离散，明天就是图论考试，加油！
基于老师的PPT和清华大学出版社的《离散数学（第五版）》
第六章 特殊的图
6.1 二部图（偶图）
定义
将顶点集分为两个不相交的子集V₁和V₂（这两个子集被称为是互补顶点子集），使得边集中的任何一条边的两个端点分别属于V₁和V₂。
充要条件
当且仅当无向图G中 没有长度为奇数的回路。
匹配
- 极大匹配：再加入任何一条边便不再是匹配的M。
- 最大匹配：边数最多的匹配。
- 匹配数：最大匹配中的边的条数。
- 完美匹配：每个顶点都是饱和点的M。
- 饱和点：与匹配中的边关联的点（如果不关联就是非饱和点）。
- 完备匹配：若V₁与V₂中较小的一个集合（假定是V₁）中的点被最大匹配的边全部关联，那么M就是G中V₁到V₂的完备匹配。
Hall定理（存在完备匹配的充分必要条件）
设二部图G = (V₁, V₂, E) ，|V₁| ≤ |V₂|，当且仅当 V₁中任意k个顶点至少邻接V₂中的k个顶点 时，G中存在从V₁到V₂的完备匹配。（被称为相异性条件）。
Hall定理的推论
t条件：
- V₁中的每个顶点至少关联t条边。
- V₂中的每个顶点至少关联t条边。
则G中存在从V₁到V₂的完备匹配。
6.2 欧拉图
定义
存在欧拉回路的图叫做欧拉图。
- 欧拉回路（通路）：经过无向图/有向图中每条边一次且仅一次并行遍入图中每个定点的回路（通路）。
存在欧拉回路的充要条件
无向图中：
有向图中：
有欧拉通路而无欧拉回路的充要条件
无向图中：
有向图中：
- 当且仅当 G是连通的；
- 且除了两个顶点外，其余顶点入度均等于出度；
- 而这两个顶点中，有一个顶点的 入度=出度+1（终点），另一个顶点的 出度=入度+1（起点）。
6.3 哈密顿图
定义
存在哈密顿回路的图。
- 哈密顿回路（通路）：经过图中每个顶点一次且仅一次的回路（通路）。
哈密顿图的特性
边数 > 点数。 p（G - V₁） ≤ |V₁|。 p（G - V₁） ≤ |V₁| + 1。 哈密顿图的充分条件
设G是n（n ≥ 3）阶无向简单图； 有向哈密顿图的充分条件
设D是n（n ≥ 2）阶有向图D；
本文内容的应用
竞赛图：比赛安排流程（任意两个队比赛一次，没有平局，用有向图描述比赛的结果）。 格雷码：确定圆盘停止旋转的位置（一组n位数，相邻的两个一级最后一个和第一个之间只有一位不同）。
6.4 平面图
定义
能画在平面上使得除顶点处外没有边交叉出现的图。
面
- 外部面/无限面：面积无限的区域。
- 内部面/有限面：面积有限的区域。
- 边界：包围面R的所有边构成的回路。
- 次数：边界的次数的总和。
平面图的特性
极大平面图
- 简单平面图；
- 任意两个不相邻的顶点之间再加一条边，所得图为非平面图时，G是极大平面图。
判断Gₙ（n ≥ 3）阶平面图是否为极大平面图
G是连通的； 每个面的次数都是3。
极小平面图
- G是个非平面图；
- G中任意删除一条边，所得图为平面图时，G是极小非平面图。
欧拉公式
设G是个任意的连通平面图，有：
推广
- 设G是个有p个连通分支的平面图，有：
- 顶点数 - 边数 + 面数 = 连通分支数 + 1（p ≥ 2）。
平面图的边界公式
- 如果G是个连通的平面图且每个面的次数至少为l（l ≥ 3），有：
- 如果G是个p（p ≥ 2）个连通分支的平面图且每个面的次数至少为l（l ≥ 3），有：
库拉图斯基定理
- 一个图是平面图，当且仅当他没有可收缩到K₅的子图，也没有可收缩到K₃,₃的子图。
平面图的必要条件
平面图的所有面的次数之和 = 边数 × 2。 面着色：任何平面图都是4-可着色的。 对偶图
- 每个面对应一个点，而原本的图中的边就作为新定义下的点的连接的线。
本部分内容的应用
- 地图：比如国家地理图，利用平面嵌入来展示地理信息。
转载地址：http://dwekk.baihongyu.com/