0%

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

平面图的概念

可平面图

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

可平面图的性质

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

面和边界

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

极大可平面图

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

Euler公式及其应用

Euler公式

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

Euler公式的应用

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

平面图的对偶图

对偶图

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

对偶图的性质

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