【知识总结】 平面图的概念

平面图的概念

可平面图

• 定义：能画在平面上，且任意两边不交叉
• 交叉：包含端点以外的其他公共点
• 这个画法叫做一种平面嵌入
• 画出来的结果是一个平面图
• 两个很重要的不可平面图，是

可平面图的性质

• 可平面图的子图是可平面图
• 环边和重边不影响可平面图

面和边界

• 面
  • 平面图的边将平面划分出的极大区域
  • 面数：
• 无限面
  • 面积无限的面，又称外部面
  • 平面图只有一个无限面
  • 每个非外部面都能按照另一种平面嵌入变为外部面
• 边界
  • 包围一个面的所有边
• 面的度数
  • 边界上边的数量，又称长度
  • 只在一个面的边界上的边（即割边）计两次
  • 图的所有面的度数和=所有边数目的两倍
• 平面图G是二部图的充要条件是任意一个面的度数是偶数

极大可平面图

• 极大可平面图：
  • 简单可平面图
  • 任意增加一条连接不相邻顶点的边都不再是可平面图
• 性质
  • 一定是连通图
  • 不能有割点或割边（时）
• 对于至少含3个顶点的极大平面图，其每个面的度数必定都是3

Euler公式及其应用

Euler公式

• 对于连通的平面图，
• 对于具有个连通分支的平面图，

Euler公式的应用

• 设是连通的平面图，且每个面的度数至少为，则
• 设是具有个连通分支的平面图，各个面的度数至少为，则
• 和都是不可平面图
• 设是的简单平面图，则
• 设是的简单平面图，则
• 设是的极大简单平面图，则
• 设是的简单连通图，则是极大平面图当且仅当的每个面的度数均为3
• 不可能用正圆画出4个集合的Venn图

平面图的对偶图

对偶图

• 面点
• 公共边界上的边连接两点的边
• 割边环
• 记作

对偶图的性质

• 的割边对应的环边，的环边对应的割边
• 是连通图
• 是平面图
• 定理：设是具有个连通分支的平面图的对偶图，则
  • 设的顶点位于的面中，则
• 同构图的对偶图不一定同构
• 对于连通的平面图，其对偶图的对偶图还是，即