平面图

• 可平面图 := 平面画出 $\land$ 边边交点只能为顶点
• 面/域 := 圈子图围出区域
  • 边界 := 子图回路
  • 度 := 圈子图の回路长度
• 欧拉公式 := 已知 $G$ 是平面度，有 $n$ 个点，$m$ 条边，$d$ 个面，面最小度为 $l$

  • 则 $n+m-d=2$

    1. 生成树 $T$ 有 $n-1$ 条边，$1$ 个外部面
    2. $G-T$ 有 $m-n+1$ 条边
    3. $G-T$ 每条边生成一个内部面
    4. 共 $d=1+(m-n+1)=m-n+2$ 个面

  • 推论 $$m\leq\frac{l}{l-2}(n-2)$$

    1. 面度数和 = 边数 $\times2$
    2. $m=\sum_{i=1}^{d} l_{i}\geq ld=l(n+m-2) \implies m\leq\frac{l}{l-2}(n-2)$
• 极大平面图 := 平面图 $\land$ 加任意边导致不是平面图
  1. = 三角剖分网格
  2. 任意点与任意相邻点构成回路
  3. $3d=2m$
  4. $m=3n-6$ 简单平面图 $m\leq 3n-6$
  5. $d=2n-4$ 简单平面图 $d\leq 2n-4$
• 可平面图判定
  • $m\leq\frac{l}{l-2}(n-2)$
  • $m\leq3n-6$
  • $d\leq 2n-4$
  • 库拉图斯基定理 := 可平面图 $\Leftrightarrow$ 无 $K$ 型子图

欧拉图

• 欧拉通路 := 经过所有边の简单通路
• 欧拉回路 := 经过所有边の简单回路
• 半欧拉图 := 存在欧拉通路の图
• 欧拉图 := 存在欧拉回路の图
• 欧拉判定
  • 存在欧拉回路 $\Leftrightarrow$ 所有点度数为偶
  • 存在欧拉通路 $\Leftarrow$ 恰有 2 个奇度顶点

哈密尔顿图

• 哈密尔顿通路 := 经过所有点の初级通路
• 哈密尔顿回路 := 经过所有点の初级回路
• 半哈密尔顿图 := 存在哈密尔顿通路の图
• 哈密尔顿图 := 存在哈密尔顿回路の图
• 极长通路 := 两端无法再延长の简单通路
• 初级极长通路 := 两端无法再延长の初级通路
• 哈密尔顿判定
  • $n$($n\geq 2$) 阶简单图，任意两个点度数和 $\geq n-1$ $\implies$ 存在哈密尔顿通路
  • $n$($n\geq 3$) 阶简单图，任意两个点度数和 $\geq n$ $\implies$ 存在哈密尔顿回路
  • $n$($n\geq 3$) 阶简单图，任意点度数 $\geq n/2$ $\implies$ 存在哈密尔顿回路