图的基本概念

有向图：$G = (V, E)$，顶点集、顶点、边集、有向边、起点、终点

基图：不考虑边的方向得到的无向图。

顶点数 $|V(G)|$，边数 $|E(G)|$，顶点数也称图的阶数。

点与边关联，点与点邻接。

无向图每个点的度数 $d(v)$，有向图每个点的入度 $d^-(v)$ 和出度 $d^+(v)$。

握手定理：

  • 对于无向图，$\displaystyle \sum_{v \in V} d(v) = 2|E|$
  • 对于有向图，$\displaystyle \sum_{v \in V} d^-(v) = \sum_{v \in V} d^+(v) = |E|$
  • 如果对等式在 $\pmod 2$ 意义下讨论，则知奇度顶点的个数必为偶数。

二分图 / 二部图：

  • 二部图：存在一个划分 $V = V_1 \cup V_2,\ V_1 \cap V_2 =\emptyset$，使得 $V_1, V_2$ 内部没有边。
  • 完全二部图：二部图中，$V_1$ 中任意顶点与 $V_2$ 中任意顶点都有边相连。

子图：

  • 子图：$G’(V’, E’)$ 满足 $V’ \subseteq V,\ E’ \subseteq E$
  • 生成子图：$G’(V’, E’)$ 满足 $V’=V,\ E’ \subseteq E$
  • 导出子图：$G’(V’, E’)$ 满足 $V’ \subseteq V$，且 $E’ = {e\mid e = (u,v) \land u, v \in V’ \land e \in E}$.

图的操作：

  • 删点则要删除顶点相连的边，删边则不删除顶点。
  • 补图：$\overline{G} = (V’, E’)$ 满足 $V’ = V,\ E \cup E’ = E(K_n),\ E \cap E’ = \emptyset$

图同构：$E = (V,E)$ 和 $E’ = (V’,E’)$ 同构，则存在双函数 $f: V \to V’$，使得 $g: E \to E’$ 描述为 $g((u, v)) = (f(u), f(v))$ 也是双函数。

  • $\forall e = (u, v) \in E,\ !\exists e’ = (f(u), f(v)) \in E'$
  • $\forall e’ = (u, v) \in E’,\ !\exists e = (f^{-1}(u), f^{-1}(v)) \in E$

特殊图

特殊图：

  • 简单图：没有自环和重边的图。
  • $k\ -$ 正则图：所有顶点度数都为 $k$ 的图，边数为 $nk / 2$.
  • $n\ -$ 阶完全图：两两都有边
  • $n\ -$ 阶圈：每个点度数都为 $2$，且联通
  • $n\ -$ 阶轮：$n\ -$ 阶圈基础上，加一个点连向所有的点
  • $n\ -$ 阶超立方：$2^n$ 个顶点，每个顶点度数为 $n$，每个顶点用长为n的二进制编码，两个顶点之间有边当且仅当它们的编码只有一位不同

平面图

可平面图：可以把 $G$ 画到平面上，且任意两条边的除顶点外没有其他交点。

平面图：可平面图在平面上的一个画法。

树是可平面图，因为没有回路。

面、域、边界、度、外部面、内部面

握手定理：平面图所有面的度数之和是边数的两倍。

欧拉公式：若 连通 平面图有 $n$ 个顶点、$m$ 条边和 $d$ 个面，那么 $n - m + d = 2$

极大平面图：平面图，满足在任意两个不相邻顶点加一条边后是非平面图。 性质：

  • 连通图、没有桥
  • 每个面都由 $3$ 条边组成，故 $3d = 2m$，$m = 3n-6,\ d = 2n - 4$

因此对于所有 连通 平面图，满足 $m \le 3n - 6,\ d \le2n-4$

平面图边数上界：

  • 若每个面的度数 $\ge l\ (l \ge 3)$，，那么 $\displaystyle m \le \frac{l}{l - 2} (n - 2)$
  • 对于 $n \ge 3$ 的联通简单平面图有 $m \le 3n - 6$
    • 证明：每个面至少是三角形，故 $\displaystyle 2 = n - m + f \le n - m + \frac{2}{3} m = n - \frac{1}{3} m \Rightarrow m \le 3(n - 2)$
  • 对于 $n \ge 3$，且无三角面的联通简单平面图有 $m \le 2n - 4$
    • 证明：每个面至少是四边形，故 $\displaystyle 2 = n - m + f \le n - m + \frac{1}{2} m = n - \frac{1}{2} m \Rightarrow m \le 2(n - 2)$

平均度公式：$\displaystyle \overline{d} = \frac{2m}{n} \le \frac{6(n - 2)}{n} < 6$

库拉图斯基定理：$G$ 是可平面的，当且仅当 $G$ 不存在 $K_5$ 或 $K_{3,3}$ 型子图。

  • $K^{(1)}$ 型图：在完全图 $K_5$ 的边上添加一些度为 $2$ 的点得到的图。
  • $K^{(2)}$ 型图：在完全二部图 $K_{3,3}$ 的边上添加一些度为 $2$ 的点得到的图。

欧拉图

欧拉回路→欧拉图，欧拉通路→半欧拉图

欧拉图充要条件：所有顶点的度数都为偶数

半欧拉图充要条件：只有两个度为奇数，其余为偶数

哈密顿图

哈密顿回路→哈密顿图，哈密顿通路→半哈密顿图

判定的充分条件：如果任意两个顶点度数之和 $\ge n -1$，则 $G$ 存在哈密顿通路

旅行商问题（TSP）：在带权连通图中寻找最短哈密顿通路。这是典型 NP 问题。

图的连通性

路径：

  • 通路、回路
  • 简单：不含重复的边
  • 初级：不含重复的顶点
  • 路径：初级通路
  • 圈：初级回路
  • 如果是初级的，那么一定是简单的
  • 如果从 $u$ 到 $v$ 有通路，则必有长度 $\le n - 1$ 的初级通路
  • 如果从 $u$ 到 $u$ 有回路，则必有长度 $\le n$ 的初级回路
  • 二部图当且仅当没有奇环。

无向图连通：

  • 连通分支：$V$ 关于可达关系 $\leftrightarrow$ 的等价类 $[u]_{\leftrightarrow} \subseteq V$ 的导出子图。
  • 连通分支数：关于可达关系的等价类数
  • 连通无向图：只有一个连通分支，$|V| - 1 \le |E| \le \dfrac{|V|(|V| - 1)}{2}$

割点与桥：

  • 点割集：删除该集合的点及其关联的边，会增加连通分支数，但是如果删除该集合的一个真子集的点及其关联的边，不会增加连通分支数；换句话说，点割集是极小的。
  • 割点：删除该点及其关联的边，会增加连通分支数
  • 点连通度：点割集的最小顶点数，称为 $k$ 连通图。
    • 完全图的点连通度为 $n - 1$
    • 非连通图的点连通度为 $0$
  • 边割集：删除该集合的边，会增加连通分支数，但是如果删除该集合的一个真子集的边，不会增加连通分支数；换句话说，边割集是极小的。
  • 桥：删除该边及其关联的边，会增加连通分支数
  • 边连通度：边割集的最小边数，称为 $r$ 连通图
    • 完全图的边连通度为 $n - 1$
    • 非连通图的边连通度为 $0$

有向图连通：

  • 强连通：对于任意两顶点 $u, v$，$u$ 可达 $v$，$v$ 可达 $u$，或者写为 $u \leftrightarrow v$.
  • 单向连通：对于任意两顶点 $u, v$，$u$ 可达 $v$ 或 $v$ 可达 $u$，至少有一个成立
  • 弱连通：基图是连通图。
  • 强连通一定是单向连通的，单向连通一定是弱连通的。

图的存储和表示

关联矩阵：$M = [m_{ij}] \in \mathbb R^{n \times m}$ ，满足

  • 对于无向图，$\displaystyle m_{ij} = \begin{cases}1,& v_i 是 e_j 的端点 \ 0,& \text{otherwise}\end{cases}$
  • 对于有向图，$m_{ij} = \begin{cases} 1, & v_i 是 e_j 的起点 \ -1, & v_i 是 e_j 的终点 \0, & \text{otherwise}\end{cases}$

邻接矩阵：$A = [a_{ij}] \in \mathbb R^{n \times n}$，满足 $a_{ij}$ 为边 $(v_i, v_j)$ 的数量。无向图的邻接矩阵是关于对角线对称的。

可达矩阵：$\displaystyle B = \bigcup_{k = 1}^{\infty} A^k$，邻接矩阵的传递闭包。

图的遍历

深度优先遍历（DFS）、广度优先遍历（BFS）