文档
数学
离散数学
平面图

平面图

  • 平面图
    • 定义
      • 可平面图 / 平面图：可以把边无交地画在平面上的图。
      • 平面嵌入：画出的无边相交的平面图。
      • 非平面图：无平面嵌入的无向图。
    • 性质
      • K1,K2,K3,K4,K5−e,K1,n,K2,nK_1,K_2,K_3,K_4,K_5-e,K_{1,n},K_{2,n} 是平面图，K5,K3,3K_5,K_{3,3} 是非平面图。
      • 平面图的子图是平面图，非平面图的母图是非平面图。
      • 平面图加入平行边或环后还是平面图。
    • 面
      • 面：平面图将平面划分出的区域。
      • 无限面 / 外部面：面积无限大的面，记作 R0R_0。
      • 有限面 / 内部面：面积有限大的面，记作 R1,R2,…R_1,R_2,\dots。
      • 边界：包围面的回路。
        • 边界可以是各种回路，也可以是多个非连通的回路的并。
      • 次数：面的边界的长度，记作 deg⁡(Ri)\deg(R_i)。
      • ∑i=0r−1deg⁡(Ri)=2m\displaystyle\sum_{i=0}^{r-1} \deg (R_i) = 2m。
      • 简单图没有次数为 11 或 22 的面（分别对应环和平行边）。
    • 极大平面图
      • 极大平面图：已知简单平面图 GG，若在任意不相邻节点间添加一条边后变为非平面图。
      • 规定已无不相邻节点的简单平面图也是极大平面图。
      • 极大平面图是连通的，n (n≥3)n\ (n\ge 3) 阶极大平面图没有割点和桥。
      • 已知 GG 为简单连通图，GG 为极大平面图   ⟺  \iff GG 的每个面的次数均为 33。
    • 极小非平面图
      • 极小非平面图：已知非平面图 GG，若任意删除一条边后变为平面图。
      • K5,K3,3K_5,K_{3,3} 是极小非平面图。
      • 极小非平面图是简单图。
  • 欧拉公式
    • 内容
      • 已知连通平面图 GG 的结点数、边数、面数分别为 n,m,rn,m,r，则 n−m+r=2n-m+r=2。
      • 已知平面图 GG 的结点数、边数、面数、连通分支数分别为 n,m,r,k=p(G)n,m,r,k=p(G)，则 n−m+r=k+1n-m+r=k+1。
    • 相关定理
      • 连通平面图 GG 有 deg⁡(G)≥l≥3\deg(G)\ge l\ge 3，则 m≤ll−2(n−2)m\le \dfrac{l}{l-2}(n-2)。
      • 平面图 GG 有 k=p(G),deg⁡(G)≥l≥3k=p(G),\deg(G)\ge l\ge 3，则 m≤ll−2(n−k−1)m\le \dfrac{l}{l-2}(n-k-1)。
      • 已知 GG 为 n (n≥3)n\ (n\ge 3) 阶 mm 条边的极大平面图，则 m=3n−6m=3n-6。
      • 已知 GG 为 n (n≥3)n\ (n\ge 3) 阶 mm 条边的简单平面图，则 m≤3n−6m\le 3n-6。
      • 已知 GG 为简单平面图，则 δ(G)≤5\delta(G)\le 5。
  • 平面图的判定
    • Kuratowski 定理
      • 插入 22 度结点：已知 e=(u,v)e=(u,v)，删除 ee 并增加 w,(w,u),(w,v)w,(w,u),(w,v)。
      • 消去 22 度结点：插入 22 度结点的逆过程。
      • 同胚：G1G_1 与 G2G_2 同构或经过反复插入或消去 22 度结点后同构。
      • 收缩边：已知 e=(u,v)e=(u,v)，删除 ee 并增加 ww，将与 u,vu,v 相邻的点连接到 ww。
      • GG 是平面图   ⟺  \iff GG 中不含与 K5K_5 或 K3,3K_{3,3} 同胚的子图。
      • GG 是平面图   ⟺  \iff GG 中不含可以收缩为 K5K_5 或 K3,3K_{3,3} 的子图。
    • 其他方法
  • 平面图的对偶图
    • 定义
      • 已知 GG 为平面嵌入，按照以下方式构造对偶图 G∗G^*
        • GG 中的面 RiR_i 对应 G∗G^* 中结点 vi∗v^*_i。
        • GG 中的边 eke_k 是两个面 Ri,RjR_i,R_j 的边界，则在 G∗G^* 中连边 ek∗=(Ri,Rj)e^*_k=(R_i,R_j)。
    • 性质
      • G∗G^* 为平面嵌入。
      • G∗G^* 是连通图。
      • 已知 ee 与 e∗e^* 对应
        • 图像上，e∗e^* 只与 ee 相交，不与其他边相交。
        • 若 ee 是环，则 e∗e^* 是桥，若 ee 是桥，则 e∗e^* 是环。
      • 在多数情况下，G∗G^* 为多重图。
      • 同构的平面图的对偶图不一定是同构的。
      • GG 有 kk 个连通分支时，n,m,rn,m,r 和 n∗,m∗,r∗n^*,m^*,r^* 的关系：
        • n∗=r,m∗=m,r∗=n−k+1n^*=r,m^*=m,r^*=n-k+1，当 k=1k=1 是有 r∗=nr^*=n。
        • G∗G^* 中 vi∗v^*_i 与 GG 中 RiR_i 对应，则 dG∗(vi∗)=deg⁡(Ri)d_{G^*}(v^*_i)=\deg(R_i)。
    • 自对偶图
      • 若 G≅G∗G\cong G^*，则 GG 为自对偶图。
      • nn 阶轮图 WnW_n：在 n−1n-1 边形内放置 11 个结点，此结点与多边形顶点都相邻。
      • 轮图都是自对偶图。
欧拉图和哈密顿图树