图论理论基础和存储方式的实现

🕗 发布于 2024-12-04 15:50 图论

图论1

图论 (Graph theory) 是数学的一个分支，图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

1、图的理论基础

图（Graph）

用大写字母（如 $G$ ）表示图，通常记为 $G = (V, E)$ ，其中 $V$ 表示顶点集， $E$ 表示边集。例如：设 $G = (V, E)$ 是一个无向图， $V$ 包含多个顶点， $E$ 包含连接这些顶点的边。

相邻（Adjacent）

若顶点 $u$ 和 $v$ 相邻，可表示为： $\sim v$ 。例如：在图 $G$ 中，若顶点 $u$ 和 $v$ 之间有边相连，则有 $\sim v$ 。

简单图（Simple Graph）

设 $G = (V, E)$ 为简单图，特点是不存在自环（即不存在边 $e = (u, u)$ ， $u\in V$ ）和多重边（任意两顶点间不存在多条相同边），可描述为： $G = (V, E)$ 是简单图，满足无自环与多重边条件。

度数（Degree）

无向图中顶点度数：无向图里顶点 $v$ 的度数用 $\deg(v)$ 表示，比如：在无向图 $G$ 中，顶点 $v$ 的度数记为 $\deg(v)$ ，其值等于与 $v$ 相连的边的数量。
有向图中顶点度数：有向图中顶点 $v$ 的入度表示为 $\text{indeg}(v)$ ，出度表示为 $\text{outdeg}(v)$ 。例如：在有向图 $G$ 中，顶点 $v$ 的入度为 $\text{indeg}(v)$ ，出度为 $\text{outdeg}(v)$ ，度数可结合二者考量。

路径（Path）

用 $P=(v_0,v_1,\cdots,v_n)$ 表示从顶点 $v_0$ 出发，依次经过 $v_1,\cdots,v_n$ 这些顶点的路径。例如：在图 $G$ 中，存在路径 $P=(v_1,v_2,v_3)$ ，即从顶点 $v_1$ 出发，依次经过 $v_2$ 和 $v_3$ 的路线。

子图（Subgraph）

设 $G=(V,E)$ 是原图，$G'=(V',E')$ 是它的子图，关系表示为：$V'\subseteq V$ 且 $E'\subseteq E$，同时 $E'$ 中边的端点都在 $V'$ 中，则 $G'=(V',E')$ 为 $G$ 的子图。

比如：已知图 $G = (V, E)$ ，取 $V^{'}$ 为 $V$ 的部分顶点集， $E^{'}$ 为相应连接这些顶点的部分边集，满足条件后， $G^{'} = (V^{'}, E^{'})$ 就是 $G$ 的子图。

连通（Connected）

无向图连通：设 $G = (V, E)$ 为无向图，若对任意 $u,v\in V$ ，都存在一条路径连接 $u$ 和 $v$ ，则称 $G$ 是连通的，可写成： $\forall u,v\in V$ ，存在路径连接 $u$ 与 $v$ ，则 $G$ 连通。
有向图连通相关（强连通和弱连通）：
- 强连通：对于有向图 $G = (V, E)$ ，若对任意 $u,v\in V$ ，都存在从 $u$ 到 $v$ 的有向路径以及从 $v$ 到 $u$ 的有向路径，则 $G$ 是强连通的，即： $\forall u,v\in V$ ，存在从 $u$ 到 $v$ 及从 $v$ 到 $u$ 的有向路径，则 $G$ 强连通。
- 弱连通：若把有向图 $G = (V, E)$ 的边看作无向边时图是连通的，则 $G$ 是弱连通的，表示为：将有向图 $G = (V, E)$ 的边视为无向边时图连通，则 $G$ 弱连通。

无向图（Undirected Graph）

直接用 $G=(V,E)$ 表示无向图，并说明其边无方向特点。

如： $G = (V, E)$ 为无向图，其边没有方向，即对边 $e=(u,v)\in E$ ， $u$ 与 $v$ 的关系是对称的。

有向图（Directed Graph）

用 $G = (V, E)$ 表示有向图，强调边有方向。

例如： $G = (V, E)$ 为有向图，边 $e=(u,v)\in E$ 有方向，从 $u$ 指向 $v$ ，表示一种单向关系。

割（Cut）

边割（针对无向图）：设 $G = (V, E)$ 是连通无向图，若存在边子集 $E'\subseteq E$ ，去掉 $E^{'}$ 后使得图不再连通，则 $E^{'}$ 是 $G$ 的一个边割，可表示为： $G = (V, E)$ 连通无向图， $\exists E'\subseteq E$ ，去掉 $E^{'}$ 后 $G$ 不连通，则 $E^{'}$ 为 $G$ 的边割。
点割（针对无向图）：对于连通无向图 $G = (V, E)$ ，若存在顶点子集 $V'\subseteq V$ ，去掉 $V^{'}$ 以及和这些顶点相关联的边后使得图不再连通，则 $V^{'}$ 是 $G$ 的一个点割，写成： $G = (V, E)$ 连通无向图， $\exists V'\subseteq V$ ，去掉 $V^{'}$ 及相关边后 $G$ 不连通，则 $V^{'}$ 为 $G$ 的点割。

稀疏图/稠密图（Sparse Graph / Dense Graph）

稀疏图：对于图 $G = (V, E)$ ，若 $\ll |V|^2$ （这里 $\ll$ 示意边数量远小于顶点数量平方的大概关系），则 $G$ 为稀疏图，如： $G = (V, E)$ ，当 $\ll |V|^2$ 时， $G$ 为稀疏图。
稠密图：与稀疏图对应，若 $∣ E ∣$ 接近 $V|^2$ 量级，可写成： $G = (V, E)$ ，当 $∣ E ∣$ 接近 $V|^2$ 时， $G$ 为稠密图。

补图（Complement Graph）

设 $G = (V, E)$ 是无向简单图，其补图 $\overline{G}=(V,\overline{E})$ ，其中 $\overline{E}$ 包含了所有不在 $E$ 中但两端点在 $V$ 中的边，可表示为： $G = (V, E)$ 为无向简单图，其补图 $\overline{G}=(V,\overline{E})$ ， $\overline{E}=\{(u,v)\mid u,v\in V,(u,v)\notin E\}$ 。

反图（Inverse Graph）

对于有向图 $G = (V, E)$ ，其反图 $G^{-1}=(V,E^{-1})$ ，这里 $E^{-1}$ 是把 $E$ 中每条边的方向都反转所得到的边集，写成： $G = (V, E)$ 为有向图，其反图 $G^{-1}=(V,E^{-1})$ ， $E^{-1}=\{(v,u)\mid (u,v)\in E\}$ 。

特殊的图

完全图（Complete Graph）：

无向完全图：用 $K_n$ 表示 $n$ 个顶点的无向完全图，其边数为 $\frac{n(n - 1)}{2}$ 。例如： $K_5$ 是有 $5$ 个顶点的无向完全图，边数为 $\frac{5\times(5 - 1)}{2}=10$ 。
有向完全图：用 $D_n$ 表示 $n$ 个顶点的有向完全图，其边数为 $n (n - 1)$ 。
树（Tree）：树可描述为无向连通且无环的图，记为： $T = (V, E)$ 为树，即 $T$ 是无向连通且无环的图。
二分图（Bipartite Graph）：设顶点集 $V$ 可分成两个互不相交的子集 $V_1$ 和 $V_2$ ，使图中每条边的两个端点分别属于 $V_1$ 和 $V_2$ ，可写成： $G = (V, E)$ 为二分图， $\exists V_1,V_2\subseteq V$ ， $V_1\cap V_2=\varnothing$ ，且 $\forall e=(u,v)\in E$ ， $u\in V_1$ 且 $v\in V_2$ 或 $u\in V_2$ 且 $v\in V_1$ 。

同构（Isomorphism）

设 $G = (V, E)$ 和 $G^{'} = (V^{'}, E^{'})$ 是两个图，若存在双射函数 $\to V'$ ，使得对于任意的 $\in V$ ， $\in E$ 当且仅当 $\in E'$ ，则称 $G$ 和 $G^{'}$ 是同构的，表示为： $G = (V, E)$ ， $G^{'} = (V^{'}, E^{'})$ ，若 $\exists f: V \to V'$ 双射，满足 $\forall u,v\in V$ ， $(u,v)\in E \Leftrightarrow (f(u),f(v))\in E'$ ，则 $G$ 与 $G^{'}$ 同构。

无向简单图的二元运算

并运算（Union）：设 $G_1=(V_1,E_1)$ 和 $G_2=(V_2,E_2)$ 是两个无向简单图，它们的并 $G_1\cup G_2=(V_1\cup V_2, E_1\cup E_2)$ ，可写成： $G_1=(V_1,E_1)$ ， $G_2=(V_2,E_2)$ ，则 $G_1\cup G_2=(V_1\cup V_2, E_1\cup E_2)$ 。例如：已知 $G_1$ 和 $G_2$ 两个无向简单图，计算它们的并图 $G_1\cup G_2$ 。

交运算（Intersection）： $G_1\cap G_2=(V_1\cap V_2, E_1\cap E_2)$ ，表示为： $G_1=(V_1,E_1)$ ， $G_2=(V_2,E_2)$ ，则 $G_1\cap G_2=(V_1\cap V_2, E_1\cap E_2)$ 。

差运算（Difference）： $G_1 - G_2=(V_1, E_1 - E_2)$ ，写成： $G_1=(V_1,E_1)$ ， $G_2=(V_2,E_2)$ ，则 $G_1 - G_2=(V_1, E_1 - E_2)$ 。

特殊的点集/边集

支配集（Dominating Set）

在无向图 $G = (V, E)$ 中，顶点子集 $D\subseteq V$ 称为支配集，若对任意顶点 $v\in V - D$ ，都存在顶点 $u\in D$ 使得 $u$ 和 $v$ 相邻，可表示为： $G = (V, E)$ 无向图， $\exists D\subseteq V$ ， $\forall v\in V - D$ ， $\exists u\in D$ ， $\sim v$ ，则 $D$ 为支配集。

边支配集（Edge Dominating Set）

在无向图 $G = (V, E)$ 中，边子集 $F\subseteq E$ 称为边支配集，若对任意边 $e\in E - F$ ，都存在边 $f\in F$ 与 $e$ 相邻（共享端点），写成： $G = (V, E)$ 无向图， $\exists F\subseteq E$ ， $\forall e\in E - F$ ， $\exists f\in F$ ， $e$ 与 $f$ 共享端点，则 $F$ 为边支配集。

独立集（Independent Set）

在无向图 $G = (V, E)$ 中，顶点子集 $I\subseteq V$ 称为独立集，若 $I$ 中任意两个顶点都不相邻，即： $G = (V, E)$ 无向图， $\exists I\subseteq V$ ， $\forall u,v\in I$ ， $u$ 与 $v$ 不相邻，则 $I$ 为独立集。

匹配（Matching）

在无向图 $G = (V, E)$ 中，边子集 $M\subseteq E$ 称为匹配，若 $M$ 中的边两两之间没有公共端点，可表示为： $G = (V, E)$ 无向图， $\exists M\subseteq E$ ， $\forall e_1,e_2\in M$ ， $e_1$ 与 $e_2$ 无公共端点，则 $M$ 为匹配。

点覆盖（Vertex Cover）

在无向图 $G = (V, E)$ 中，顶点子集 $C\subseteq V$ 称为点覆盖，若图 $G$ 中的每条边至少有一个端点在 $C$ 中，写成： $G = (V, E)$ 无向图， $\exists C\subseteq V$ ， $\forall e\in E$ ， $\exists v\in C$ ， $v$ 为 $e$ 的端点，则 $C$ 为点覆盖。

边覆盖（Edge Cover）

在无向图 $G = (V, E)$ 中，边子集 $L\subseteq E$ 称为边覆盖，若对于任意顶点 $v\in V$ ，都存在边 $e\in L$ 使得 $v$ 是 $e$ 的端点，可表示为： $G = (V, E)$ 无向图， $\exists L\subseteq E$ ， $\forall v\in V$ ， $\exists e\in L$ ， $v$ 为 $e$ 的端点，则 $L$ 为边覆盖。

团（Clique）

在无向图 $G = (V, E)$ 中，顶点子集 $K\subseteq V$ 称为团，若 $K$ 中任意两个顶点都相邻，即 $K$ 所诱导出的子图是完全图，可表示为： $G = (V, E)$ 无向图， $\exists K\subseteq V$ ， $\forall u,v\in K$ ， $\sim v$ ，则 $K$ 为团。

图的矩阵表示(存储方式)

邻接矩阵（Adjacency Matrix）

对于一个无向图 $G = (V, E)$ ，设顶点集 $\{v_1, v_2, \cdots, v_n\}$ ，其邻接矩阵 $A$ 是一个 $n\times n$ 的矩阵，其中元素 $a_{ij}$ 定义为：若顶点 $v_i$ 和 $v_j$ 相邻，则 $a_{ij} = 1$ （对于无向简单图）；若不相邻，则 $a_{ij} = 0$ 。

用公式表示为： $a_{ij} = \begin{cases}1, & v_i \sim v_j\text{相邻} \\ 0, & v_i \sim v_j\text{不相邻}\end{cases}$

例如，对于一个简单的三角形形状的无向图，其邻接矩阵为： $\begin{pmatrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0\end{pmatrix}$ 。

对于有向图，若存在从顶点 $v_i$ 指向 $v_j$ 的边，则 $a_{ij} = 1$ ，否则 $a_{ij} = 0$ 。其邻接矩阵能反映出有向图中顶点之间的有向连接关系。

关联矩阵（Incidence Matrix）

设无向图 $G = (V, E)$ ，顶点集 $\{v_1, v_2, \cdots, v_n\}$ ，边集 $\{e_1, e_2, \cdots, e_m\}$ ，其关联矩阵 $M$ 是一个 $n\times m$ 的矩阵，元素 $m_{ij}$ 定义如下：若顶点 $v_i$ 与边 $e_j$ 关联（即 $v_i$ 是 $e_j$ 的一个端点），则 $m_{ij} = 1$ ；若不关联，则 $m_{ij} = 0$ 。

用公式表示为： $m_{ij} = \begin{cases}1, & \text{如果} v_i \text{关联} e_j \\ 0, & \text{如果} v_i \text{不关联} e_j\end{cases}$

例如，对于一个简单的有四条边、三个顶点的无向图，其关联矩阵可能为： $\begin{pmatrix}1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0\end{pmatrix}$ 。有向图的关联矩阵定义稍有不同，对于有向边 $e_j$ ，若顶点 $v_i$ 是边 $e_j$ 的起点，则 $m_{ij} = 1$ ；若 $v_i$ 是边 $e_j$ 的终点，则 $m_{ij} = -1$ ；若 $v_i$ 与 $e_j$ 不关联，则 $m_{ij} = 0$ 。

2、图的存储

n为图的顶点数，m为图的边数， $d^+(u)$ 为点u的出度， $d^-(u)$ 为点u的入度

2.1、直接存边

实现：

使用多个数组来存储变得起点终点和权值。

复杂度：

查询是否存在某条边： $O (m)$

遍历一个点的所有出边： $O (m)$

遍历整张图： $O (nm)$

空间复杂度： $O (m)$

注：在Kruskal算法中，需要把边按权值排序，需要直接存储边。

2.2、邻接矩阵