Basic Concept

学习图算法，先从图的 概念、定义 和 性质 先掌握。

• 图

  图是一个三元组 $⟨V(G),E(G),{\varphi }_G⟩$，其中 $V(G)$ 是一个非空的结点集合，$E(G)$ 是边集合，${\varphi }_G$ 是从边集合 $E$ 到结点集合上的函数。

  简而言之就是，图由边集、点集和边和点的关联关系组成。

{:align=center}

• 有向与无向：

  无向边：若边 $e_i$ 与结点无序偶 $(v_j,v_k)$ 相关联，则称该边为 无向边。即边所连两个结点没有顺序关系。

  有向边：若边 $e_i$ 与结点有序偶 $⟨v_j,v_k⟩$ 相关联，则称该边为 有向边。即边所连两个结点存在顺序关系。

  偶是指一对，有序偶是指有顺序关系的一对。无序偶是指没有顺序关系的一对。无序偶用 $(a,b)$ 表示，有序偶用 $⟨a,b⟩$ 表示。结点有序偶是指有顺序关系的两个结点。

  有向图：每一条边都是有向边的图称为 有向图。

  无向图：每一条边都是无向边的图称为 无向图。

  混合图：一些边有向一些边无向的图称为 混合图。

• 邻接与孤立：

  邻接点：若两个结点之间存在边相连，则这两个结点称为 邻接点。

  邻接边：若两条边关联同一个结点，则这两条边称为 邻接边。

  孤立点：不与任何结点相邻接的结点，称为 孤立结点 或 孤立点。

  零图：仅有孤立结点组成的图称为 零图。

  平凡图：仅有一个孤立结点的图称为 平凡图。

  稀疏图：边的条数 $|E|$ 不超过 $|V{|}^2$ 的图称为 稀疏图（Sparse Graph），即边数很少的图。

  稠密图：边的条数 $|E|$ 很接近 $|V{|}^2$ 的图称为 稠密图（Dense Graph），即边数很多的图。

  环：关联于同一结点的一条边称为 自回路或环。环的方向是没有意义的，因此环可以称为无向边也可以称为有向边。

• 平行边与简单图：

  平行边：连接于同一对结点间的多条边称为 平行边。

  多重图：含有平行边的图称为 多重图。

  简单图：不含有平行边和环的图称为 简单图。

  完全图：简单图中，若每一对结点间都有边相连，则该图称为 完全图。有 $n$ 个结点的无向完全图记作 $K_n$。

  定理：$n$ 个结点的无向完全图 $K_n$ 中的边数为 $\frac{1}{2}n(n-1)$，即“握手定理”。
  $\sum V=\frac{1}{2}n(n-1)$

  补图：对于图 $G$，由 $G$ 中所有节点和所有能使 $G$ 成为完全图的添加边组成的图，称为 $G$ 相对于完全图的补图，记作 $\overline{G}$。

• 权：

  权：每条边带有一个数字或者值，用于表示长度、距离、时间或其他意义，称作该边的 权。

  带权图：每条边都带有权的图称为 带权图。

  无权图：每条边不带有权的图称为 无权图。

• 子图：

  子图：设图 $G=⟨V,E⟩$，如果有图 $G^{\prime }=⟨V^{\prime },E^{\prime }⟩$，且 $E^{\prime }\subseteq ,V^{\prime }\subseteq V$，则称 $G^{\prime }$ 为 $G$ 的子图。即由原图点集和边集的一部分组成的图。

  生成子图：如果子图 $G^{\prime }$ 包含 $G$ 的所有结点，则称 $G^{\prime }$ 为 $G$ 的 生成子图。即由原图所有节点，边集一部分组成的图。

  子图的补图：对于图 $G=⟨V,E⟩$ 的子图 $G^{\prime }=⟨V^{\prime },E^{\prime }⟩$，如果给定另一个图 $G^{\prime \prime }=⟨V^{\prime \prime },E^{\prime \prime }⟩$ 使得 $E^{\prime \prime }=E-E^{\prime }$，且 $V^{\prime \prime }$ 中仅包含 $E^{\prime \prime }$ 的边所关联的结点。则称 $G^{\prime \prime }$ 是 $G^{\prime }$ 相对于 $G$ 的 补图。

• 度：

  度数：在图中，与结点 $v(v\in V)$ 关联的边的数量，称作该结点的 度数，记作 $deg(v)$。若结点上增加一个环，则度数加 2。

  定理：图中所有结点的度数和为边数的两倍。
  ${\sum }_{v\in V}deg(v)=2|E|$

  定理：图中度数为奇数的结点必定为偶数个。

  入度：有向图中，射入一个结点的边数称为该结点的 入度。

  出度：有向图中，由一个结点射出的边数称为该结点的 出度。

  定理：有向图中，所有结点的入度和等于出度和。

• 同构：

  设图 $G=⟨V,E⟩$ 及图 $G^{\prime }=⟨V^{\prime },E^{\prime }⟩$，如果存在一一对应的映射 $g$：$v_i\to v_i^{\prime }$ 且 $e=(v_i,v_j)$ 或 $e=⟨v_i,v_j⟩$ 是 $G$ 的一条边；当且仅当 $e\prime =(\mathbf{g}({\mathbf{v}}_{\mathbf{i}}),\mathbf{g}({\mathbf{v}}_{\mathbf{j}}))$ 或 $e\prime =⟨\mathbf{g}({\mathbf{v}}_{\mathbf{i}}),\mathbf{g}({\mathbf{v}}_{\mathbf{j}})⟩$ 是 $G^{\prime }$ 的一条边，则称 $G$ 与 $G^{\prime }$ 同构。

  同构的结果实际上指的是同一幅图，但是点的位置随意挪动之后生成的另一幅图，此时边会被拉伸，但依旧是原来的边。同构的目的是为了表示，在边长度可以拉伸的条件下，图形的表示并非唯一，因此同构的图在逻辑上是同一幅图。如以下这些图：

  
  {:align=center}

  若图 $G$ 无法通过挪动点的位置使之称为另一幅图 $G^{\prime }$，则二图不同构，反之则同构。但同构难以用程序验证，同构的必要不充分条件有：

  • 结点数目相同。

  • 边数相同。

  • 度数相同的结点数目相同。

  自补图：如果一个无向图同构于它的补图，则称该图为 自补图。

  定理：如果一个图是自补图，其对应完全图的边数必定为偶数。

Path and Loop

• 路：

  • 路：给定图 $G=⟨V,E⟩$，设 $v_0$，$v_1$，$\cdots$，$v_n\in V$，$e_1$，$e_2$，$\cdots$，$e_n\in E$，其中 $e_i$ 是关联于结点 $v_{i-1}$，$v_i$ 的边，交替序列 $v_0{e}_1{v}_1{e}_2\cdots e_n{v}_n$ 称为联结 $v_0$ 到 $v_n$ 的 路。

    定理：在一个具有 $n$ 个结点的图中，若从结点 $v_j$ 到 $v_k$ 存在一条路，则 $v_j$ 到 $v_k$ 间必定存在一条不多于 $n-1$ 条边的路。
    很好理解，其实就是剔除掉路中成环的部分，最后连接两个点的边肯定只需要 $n-1$ 以下的边数。

  • 回路：$v_0$ 和 $v_n$ 分别称为路的起点和终点，边的数目 $n$ 称作路的长度。当 $v_0=v_n$ 时，这条路称作 回路。

  • 迹：若一条路中，所有的边 $e_1$、$e_2$、$\cdots$、$e_n$ 均不相同，则该路称作 迹。

  • 通路：若一条路中，所有的结点 $v_0$、$v_1$、$\cdots$、$v_n$ 均不相同，则称作 通路。

  • 圈：闭的通路，即除 $v_0=v_n$ 外，其他结点均不相同的通路称为 圈。

• 连通：

  连通：在无向图 $G$ 中，结点 $u$ 和 $v$ 之间若存在一条路，则称结点 $u$ 和 $v$ 是 连通的。

  连通分支：在无向图 $G$ 中，将结点集 $V$ 划分为非空子集 $V_1$，$V_2$，$\cdots$，$V_n$，若 $V_{?}$ 中任意两个结点都是连通的，则 $V_{?}$ 则为 $G$ 的连通分支。图 $G$ 的连通分支数记作 $W(G)$。

  连通图：若图 $G$ 仅有一个连通分支，则称该图为 连通图。

  割点：设无向图 $G=⟨V,E⟩$ 为连通图，若删除点 $v_i$ 后所得的子图不是连通图，则称该点为 割点。

  点割集：设无向图 $G=⟨V,E⟩$ 为连通图，若有点集 $V_1\subset V$，使图 $G$ 删除了 $V_1$ 的所有结点后，得到的子图不是连通图，而删除除 $V_1$ 的任何真子集后，所得到的子图仍是连通图，则称 $V_1$ 是 $G$ 的一个 点割集。

  割点集可以看作是放大的割点。如下图为割点与点割集：

  
  {:align=center}

  割边：设无向图 $G=⟨V,E⟩$ 为连通图，若删除边 $e_i$ 后所得到的子图不是连通图，则称该边为 割边 或 桥。

  边割集：设无向图 $G=⟨V,E⟩$ 为连通图，若有边集 $E_1\subset E$，使图 $G$ 删除了 $E_1$ 的所有边后，得到的子图不是连通图，而删除 $E_1$ 的任何真子集后，所得到的子图仍是连通图，则称 $E_1$ 是 $G$ 的一个边割集。

  边割集可以看作是放大的割边。如下图为割边与边割集：

{:align=center}

> 定理：结点 $v$ 是割点的充分必要条件是存在两个结点 $u$ 和 $w$，他们之间的每一条路都通过 $v$。

强连通图：在简单有向图 $G$ 中，任何一对结点都相互可达则称该图为 **强连通图**。

弱连通图：在简单有向图 $G$ 中，如果擦除所有边的方向能使得该图成为连通图，则称该图为 **弱连通图**。

单侧连通：在简单有向图 $G$ 中，任何一对结点间，至少有一个结点到另一个结点是可达的，则称这个图是 **单侧连通图**。

> 定理：一个有向图 $G$ 是强连通的，则 $G$ 中必定包含一个通过所有结点的回路。

强分图：简单有向图中具有强连通性质的最大子图称为**强分图**。

弱分图：简单有向图中具有弱联通性质的最大子图称为**弱分图**。

单侧分图：简单有向图中具有单侧连通性质的最大子图称为**单侧分图**。

> 定理：在有向图 $G=\langle V,E \rangle$ 中，每一个结点位于并只位于一个强分图中。  
> 很好理解，如果处于某一个强分图中，该分图中所有节点必定都处于该分图中，不会处于其他分图中的。

Representation

图由点集、边集和点与边的关系构成，对图进行表示，只需要记录这三者的关系即可。

Adjacency Matrix

创建一个 $V\times V$ 的矩阵，每一行表示每一个结点，每一列表示另一结点，第 $i$ 行 $j$ 列的元素 $a_{ij}$ 表示二结点间的关系，这种图的表示方法称为邻接矩阵（Adjacency Matrix），该 $n$ 阶方阵记为 $A(G)=(a_{ij})$。

对于无权图，该邻接矩阵称为 无权邻接矩阵，点 $i$ 与 $j$ 之间的关系 $a_{ij}$ 表示为：

对于带权图，该邻接矩阵称为带权邻接矩阵，点 $i$ 与 $j$ 之间的关系 $a_{ij}$ 表示为（$C(e)$ 表示边 $e$ 的权）：

对于无向图，该邻接矩阵称为无向邻接矩阵，$a_{ij}$ 的值等于 $a_{ji}$ 的值。

{:align=center}

对于有向图，该邻接矩阵称为有向邻接矩阵，一条单向边仅代表一个方向，若 $i$ 到 $j$ 存在边而 $j$ 到 $i$ 不存在边，则 $a_{ij}>0$ 而 $a_{ji}=0$

{:align=center}

邻接矩阵有几条有意思的性质：

• 邻接链表的空间耗费为 $O(V\times V)$。

• 通过邻接矩阵判断两点间是否存在边的速度是 $O(1)$，如果要判断 $v_i$ 与 $v_j$ 间是否存在边，对于无向图只需要判断 $a_{ij}$ 是否等于 0，对于有向图只需要判断 $a_{ij}\ast a_{ji}$ 是否等于 0。

• 遍历某一行/列元素即可计算该结点的度。

• 无向图的邻接矩阵是对称的，其转置矩阵为本身，因此可以缩减一半的存储空间。

• 对于零图，邻接矩阵中所有元素都为 0，因此零图的邻接矩阵是一个零矩阵。因此如果图的边越少，邻接矩阵所浪费的空间就越多，邻接矩阵更适合用于稠密图。

• 对于无权邻接矩阵进行幂方，得到结果为 $(A(G){)}^n=(a_{ij}^{(n)})$，此时 $a_{ij}^{(n)}$ 等于 $v_i$ 到 $v_j$ 的长度为 n 的路的数目。

  假设求 $a_i$ 到 $a_j$ 长度为 2 的路的数目，即求 $a_i\to a_k\to a_j$ 的路的数量，若存在某条路，则 $a_{ik}=$a{kj} = 1$，即$a_{ik} \cdot a_{kj} = 1$，若其中一端断开，则$a_{ik} * a_{kj} = 0$，因此从$a_i$到$a_j$ 长度为 2 的路的数目为：

  $a_{in}\cdot a_{nj}+a_{in}\cdot a_{nj}+\cdots +a_{in}\cdot a_{nj}={\sum }_{k=i}^n{a}_{ik}\cdot a_{kj}$

  此结果等同于矩阵 $(A(G){)}^2$ 中 $i$ 行 $j$ 列元素 $a_{ij}^{(2)}$，更高次幂以此类推。

Adjacency Linked List

创建一个 $V$ 个元素的数组，每个元素都是一个链表，每条链表表示与每个结点相连的所有其他结点。这种图的表示方法称为邻接链表，编程时通常使用这种方法表示图，使用 $Adj$ 表示该邻接链表数组。

对于无向图而言，$v_i$ 的链表中记录所有 $v_i$ 的邻接点，因此 $Adj$ 中所有邻接链表长度和为 $2E$。

{:align=center}

对于有向图而言，$v_i$ 的链表仅记录所有 $v_i$ 射出的边，因此 $Adj$ 中所有邻接链表长度和为 $E$。

{:align=center}

邻接链表同样有很多有趣的性质：

• 邻接链表的空间消耗为 $O(E+V)$。

• 邻接链表可以直接判断边的度或出度，但无法直接判断二结点是否邻接，必须遍历某结点的邻接链表才能判断。

• 对于零图，数组中所有链表都为空，因此零图的邻接链表是一个所有元素都为空的数组。因此邻接链表非常适合稀疏图的表示，

Incidence Matrix

创建一个 $E\times V$ 的矩阵 $M(G)$，每一行表示每一个结点，每一列表示每一条边，第 $i$ 行 $j$ 列的元素 $m_{ij}$ 表示 $v_i$ 与边 $e_j$ 的关系，这种图的表示法称为关联矩阵。

对于无向图，关联矩阵元素 $m_{ij}$ 为：

{:align=center}

对于有向图，关联矩阵元素 $m_{ij}$ 为：

{:align=center}

关联矩阵的性质如下：

• 关联矩阵的空间消耗为 $O(E\times V)$。

• 每一列只有 2 个元素空间会被使用。

• 遍历第 $i$ 行可判断 $v_i$ 的度数。

• 对于零图，由于不存在任何边，因此关联矩阵降为一维数组，且所有数组元素都为空。

Euler Graph

对于无孤立结点的图 $G$，如果存在一条路经过图中所有边一次且仅一次，该路就称为欧拉路。如果存在一条回路，经过图中每条边一次且仅一次，该回路称为欧拉回路。具有欧拉回路的图称为欧拉图。

{:align=center}

给定有向图 $G$，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。

性质：

• 无向图欧拉路的条件：当且仅当无向图 $G$ 是连通的，且有零个或两个奇数度结点，$G$ 具有一条欧拉路。

  简单理解必要性：欧拉路不严格要求终点必须为起点，假设图 $G$ 有 $E$ 条边，那么欧拉路必须经过这些 $E$ 条边各一次且仅一次，而每条边必定联结两个点，因此每走完一条边就会减少全局的两个度数，因此全局度数和必定是 $2E$。如果一端点为奇数度，那么该点只能作为起点或终点，因为它的最后一条邻接边要么作为射入要么作为射出，它无法作为一个中间点。因此欧拉路最多只有两个奇数度结点。如果没有奇数度结点，他就是欧拉回路。

  充分性不作证明。

• 无向图欧拉回路的条件：当且仅当无向图 $G$ 是连通的，且所有结点度数全为偶数时，$G$ 具有一条欧拉回路。

  简单理解必要性：当有奇数度的时候，该结点如果作为起点，必定无法回到该结点；该节点如果非起点，则最终只能停滞在该结点，因此无法组成欧拉回路。

  充分性不作证明。

• 有向图欧拉路的条件：当且仅当有向图 $G$ 是连通的，且除两个结点外，每个结点的入度等于出度，同时在这两个结点中，一个结点的入度比出度大一，另一个结点的入度比出度小一，$G$ 具有一条单向欧拉路。

  充分必要性不做证明。

• 有向图欧拉回路的条件：当且仅当有向图 $G$ 是连通的，且每个结点入度等于出度，$G$ 具有一条单向欧拉回路。

  充分必要性不做证明。

Hamiltonian Graph

给定图 $G$，若存在一条路经过途中每个结点恰好一次，这条路称为汉密尔顿路。若存在一条回路经过每个结点恰好一次，这条回路被称为汉密尔顿回路。具有汉密尔顿回路的图称为汉密尔顿图。

{:align=center}

性质：

• 必要条件：若图 $G=⟨V,E⟩$ 具有汉密尔顿回路，则对于点集 $V$ 的每个非空子集 $S$ 均有 $W(G-S)\le |S|$ 成立。$W(G-S)$ 表示 $G-S$ 的连通分支数。

• 充分条件：设 $G$ 具有 $n$ 个结点的简单图，如果 $G$ 中每一对结点度数之和大于等于 $n-1$，则在 $G$ 中存在一条汉密尔顿路。

• 充分条件：设 $G$ 是具有 $n$ 个结点的简单图，如果 $G$ 中每一对结点度数之和大于等于 $n$，则在 $G$ 中存在一条汉密尔顿回路。

Closure of Graph

给定图 $G=⟨V,E⟩$ 有 $n$ 个结点，若将图 $G$ 中度数之和至少是 $n$ 的非邻接结点连接起来得到图 $G^{\prime }$，对图 $G^{\prime }$ 重复上述步骤，直到不再有这样的结点对存在为止，所得到的图称为图 $G$ 的闭包。

性质：当且仅当一个简单图的闭包是汉密尔顿图是，该图是汉密尔顿图。

{:align=center}

Planar Graph

设 $G=⟨V,E⟩$ 是一个无向图，如果能够把 $G$ 的所有节点和边画在平面上，且使得任何两条边除了端点外没有其他的交点，就称 $G$ 是一个平面图。

• 面：设 $G$ 是一个连通平面图，由图中的边所包围的区域，在区域内既不包含图的结点，也不包含图的边，这样的区域称作 $G$ 的一个面。包围该面的诸条边所构成的回路称为这个面的边界。面的边界的回路长度称为面的次数。

  
  {:align=center}

  性质：面的次数之和等于平面图中边数的两倍。

• 欧拉定理：设一个连通平面图 $G$，共有 $v$ 个结点，$e$ 条边和 $r$ 个面，则有

  $v-e+r=2$

• 设 $G$ 是一个有 $v$ 个结点，$e$ 条边的连通简单平面图，若 $v\ge 3$，则 $e\le 3v-6$。

• 库拉托夫斯基（Kuratowski）定理：一个图是平面图，当且仅当它不包含与 $K_{3,3}$ 或 $K_5$ 在 2 度结点内同构的子图。

  两度结点内同构：给定两个图 $G_1$ 和 $G_2$，如果它们是同构的，或者通过插入或除去度数为 2 的结点后是同构的，则称该两图是在两度结点内同构

  
  {:align=center}

Tree

树：一个连通且无回路的无向图称为树。树中度数为 1 的结点称为树叶，度数大于 1 的结点称为分支点或内点。一个无回路的无向图称作森林，他的每个连通分支是树。

等价定义：

• 无回路的连通图

• 无回路且 $e=v-1$。

• 连通且 $e=v-1$。

• 无回路，但增加一条新边，得到一个且仅有一个回路。

• 连通，但删去任何一条边后都不连通。

• 每一对结点间有且仅有一条路。

生成树：若图 $G$ 的生成子图是一棵树，则该树称为 $G$ 的生成树。不在生成树的边称作弦。所有弦的集合称作生成树的补。

最小生成树：在图 $G$ 的所有生成树中，树杈最小的那棵生成树称作最小生成树。

{:align=center}

性质：

• 任何一颗树至少有两片树叶。

• 连通图至少有一棵生成树。

• 一条回路和任何生成树的补至少有一条公共边。

• 一个边割集和任何生成树至少有一条公共边。