11.特殊图

1.欧拉图

• 欧拉通路：通过图中所有边一次且仅一次的通路（有且仅有2个奇度顶点）
• 欧拉回路：通过图中所有边一次且仅一次的回路
• 欧拉图：具有欧拉回路的图
• 半欧拉图：具有欧拉通路而无欧拉回路的图

1. 无向图$G$ 是欧拉图 当且仅当$G$是连通图，且没有奇度顶点(所有顶点的度都是偶数)。
2. 有向图$D$ 是欧拉图 当且仅当$D$是强连通图，且每个顶点的入度等于出度。

• 例： $不是欧拉图（有奇度顶点）$ $是欧拉图（通过所有边一次且仅一次的回路，所有顶点的度都是偶数）$ $不是欧拉图（有奇度顶点）$ $不是欧拉图（有奇度顶点）$

---

2.哈密顿图

• 哈密顿通路: 经过图中所有顶点一次且仅一次的通路（有且仅有2个奇度顶点）

• 哈密顿回路: 经过图中所有顶点一次且仅一次的回路

• 哈密顿图: 具有哈密顿回路的图

• 半哈密顿图: 具有哈密顿通路而无哈密顿回路的图

• 充分条件

  1. 设$G$是$n$阶无向简单图，若对于$G$中任意不相邻的顶点$u,v$，均有 $d(u)+d(v)≥n$，则$G$是哈密顿通路。
  2. 设$G$是$n(n≥3)$阶无向简单图, 若对于$G$中任意不相邻的顶点$u,v$，均有 $d(u)+d(v)≥n$，则$G$是哈密顿回路。

• 哈密顿图判断条件

  • 存在性（充分条件，满足则一定是哈密顿图）

    1. 狄拉克定理 Dirac（简单无向图）

       $n≥3$ 个顶点，每个顶点度数 ≥ $n/2$ → 一定是哈密顿图。

    2. 奥尔定理 Ore（简单无向图）

       $n≥3$，任意不相邻两点度数和 ≥ $n$ → 一定是哈密顿图。

    3. 竞赛图

       强连通竞赛图一定是哈密顿图。

  • 非存在性（必要条件，不满足则一定不是）

    1. 必要条件（最常用） 对顶点集 $V$ 的任意非空真子集 $S$，有： $w(G-S) \leq |S|$
       • $w(G-S)$：删去 S 后连通分支数
       • $|S|$：子集顶点个数
       • 若存在 S 使得分支数 > $|S|$ → 一定不是哈密顿图。
    2. 顶点度数必要条件 存在度数为 $0/1$ 的顶点，且无法纳入回路 → 不是哈密顿图。

• 例1. 设有如下无向图, 则($\underline{A}$)是一条哈密顿通路 A. $V_7 V_1 V_6 V_5 V_4 V_3 V_2$

  B. $V_1 V_2 V_3 V_4 V_5 V_6 V_7$

  C. $V_1 V_2 V_4 V_5 V_6$

  D. $V_2 V_3 V_4$

  注:哈密顿通路: 经过图中所有顶点一次且仅一次的通路

• 例2. 设有无向图, 则($\underline{A}$)是一条哈密顿回路 A. $gabcdefg$

  B. $abcdefg$

  C. $cfabcdeg$

  D. $efgabcd$

  注: 哈密顿回路: 经过图中所有顶点一次且仅一次的回路

---

3.偶图

• 无向图 $G=< V, E>$ 为偶图（二部图）的充分必要条件是 $G$ 的所有回路的长度均为偶数。

---

4.平面图

基本概念

1. 二部图定义
   设无向图 $G=< V, E>$，若能将 $V$ 划分成$V_1$和 $V_2$（即 $V_1 \cup V_2 = V$，$V_1 \cap V_2 = \emptyset$，且 $V_1 \neq\emptyset$，$V_2 \neq\emptyset$），使得$G$中的每条边的两个端点都是一个属于 $V_1$，另一个属于 $V_2$，则称$G$为二部图。
   若$G$是二部图，$V_1$ 中的每个顶点均与 $V_2$ 中的所有顶点相邻，则称$G$为完全二部图，记为 $K_{r, s}$，其中 $r=|V_{1}|$，$s=|V_{2}|$。
2. 平面图定义
   如果能将无向图$G$ 画在平面上使得除顶点处外无边相交，则称$G$为可平面图，简称为平面图。
   • $K_{1}$ , $K_{2}$ , $K_{3}$ , $K_{4}$ 都是平面图；$K_{5}-e$（$K_{5}$ 删除任意一条边）也是平面图。
     完全二部图 $K_{1, n}(n \ge1)$，$K_{2, n}(n \ge2)$ 也都是平面图。
   • $K_{5}$ 和 $K_{3,3}$，它们都是非平面图。
     
3. 面、边界、次数
   给定平面图$G$的平面嵌入，$G$的边将平面划分成若干个区域，每个区域都称作$G$的一个面。
   包围每个面的所有边的回路组称作该面的边界，边界的长度称作该面的次数。
4. 平面图性质：平面图所有面的次数之和等于边数的两倍。
5. 极小非平面图
   若在非平面图 $G$ 中任意删除一条边，所得的图是平面图，则称$G$是极小非平面图。
   $K_{5}$ 和 $K_{3,3}$ 都是极小非平面图。
   • 例：图中$\underline{C}$是平面图

平面图的判定

• 库拉托夫斯基定理：一个图是平面图的充分必要条件是它的任何子图都不可能收缩为$K_{5}$或$K_{3,3}$。

欧拉公式

• 连通平面图$G$的顶点数、边数和面数分别为 $n$、$m$和$r$，则有$n-m+r=2$

  • 例1：设$G$是连通平面图，有5个顶点，6个面，则$G$的边数是9。
    解：$5-m+6=2$，解得 $m=9$。
  • 例2：图$G$是一个简单的连通平面图，顶点数为8，其无限面的次数为5，其余面都为三角形（次数为3），计算平面图的边数和面数。
    分析：平面图所有面的次数之和 等于边数的两倍。
    解：设平面图$G$的边数为 $m$，面数为$r$
    $$\begin{cases} 8 - m + r = 2 \\ 5 + 3 ( r - 1 ) = 2 m \end{cases} \Rightarrow \begin{cases} m=16 \\ r=10 \end{cases}$$
    解得：平面图的变数为$n=16$，面数为 $r=10$。

• 设$G$是 $n(n \ge3)$ 阶 $m$ 条边的简单平面图，则 $m \le3 n-6$。

  注：一个简单连通图，若不满足 $m \le3 n-6$，则一定是非平面图，但满足该不等式的简单连通图未必是平面图。

  • 例：设图$G$有$V$个结点，$e$条边，当 $V>3$，若不满足 $e \le3 V-6$，它一定不是平面图 $\underline{\surd}$。

---

补.最短路径问题

• 权、带权图 $G=< V, E, W>$
• 最短路径 在带权图中，$u,v \in V$，当 $u$ 和 $v$ 连通时，从 $u$ 到 $v$ 长度最短的路径，称其长度为从 $u$ 到 $v$ 的距离，记作 $d(u, v)$。 其中 $d(u, u)=0$，当$u$和$v$不连通时 $d(u, v)=+\infty$。
• 最短路径问题 给定带权图 $G=< V, E, W>$ 及顶点$u$和 $v$，求从$u$到$v$的最短路径。 注：Dijkstra算法。
  得：从 $v_{1}$ 到其余各点的最短路径和距离如下：
  $d(v_{1},v_{2})=3,\ v_1 v_2$
  $d(v_{1},v_{3})=5,\ v_1 v_2 v_5$
  $d(v_{1},v_{4})=5,\ v_1 v_4$
  $d(v_{1},v_{5})=8,\ v_1 v_2 v_3 v_5$
  $d(v_{1},v_{6})=7,\ v_1 v_4 v_6$
  $d(v_{1},v_{7})=9,\ v_1 v_4 v_6 v_7$