考研复试 | 离散数学——第六章 特殊的图
6.1 二部图
- 二部图(偶图),互补顶点子集,完全二部图(完全偶图)
- 判断是否是二部图的定理
- 匹配,极大匹配,最大匹配,匹配数,饱和点,非饱和点,完美匹配
- 完备匹配
- 存在完备匹配的充要条件(Hall定理),相异性条件,t条件
欧拉图
- 欧拉回路(欧拉通路)
哈密顿图
- 哈密顿回路(通路),哈密顿图
- 哈密顿图的必要条件
- 有哈密顿回路和哈密顿通路的充分条件
- 有向图的哈密顿通路的定理
- 竞赛图
- 格雷码
6.4 平面图
- 平面图,平面嵌入
- 面,无限面,外部面,有限面,内部面,边界,次数
- 定理6.9
- 极大平面图,极小非平面图
- 极大平面图的性质
- 欧拉公式
- 消去(插入)二度顶点
- 同胚
- 收缩边,可收缩到
- 库拉图斯基定理
- 地图着色,面着色
- 对偶图
- 四色定理