图🧀
1、基本概念🧀
-
由点（node，vertex）和连接点的边（edge）组成。图是点和边构成的网
-
用一个二元组表示 \(G(V，E)\) ，Vertices 表示顶点，Edge 表示边。
- 与一个顶点关联的边的条数称作该顶点的 度 (degree)
（1）有/无向图🧀
| 术语 | 解释 |
|---|---|
| 无向图（Undirected Graph） | 边没有方向，即 \((u, v)\) 和 \((v, u)\) 是相同的边。 |
| 有向图（Directed Graph / Digraph） | 边有方向，即 \((u, v)\) 表示从 \(u\) 指向 \(v\)。 |
（2）稀疏图/稠密图🧀
| 术语 | 解释 |
|---|---|
| 稀疏图（Sparse Graph） | 若一张图的边数远小于其点数的平方，即 \(E \ll V^2\) |
| 稠密图（Dense Graph） | 若一张图的边数接近于其点数的平方，即 \(E \approx V^2\) |
Info
稀疏图与稠密图没有严格数学定义
（3）简单图🧀
| 术语 | 解释 |
|---|---|
| 自环 (loop) | 对 \(E\) 中的边 \(e = (u, v)\)，若 \(u = v\)，则 \(e\) 被称作一个自环。 |
| 重边 (multiple edge) | 若\(E\) 中存在两个完全相同的元素（边）\(e_1, e_2\)，则它们被称作（一组）重边。 |
| 简单图 (simple graph) | 若一个图中没有自环和重边，它被称为简单图。具有至少两个顶点的简单无向图中一定存在度相同的结点。 |
| 多重图 (multigraph) | 如果一张图中有自环或重边 |
Tip
\[ E_{\max} = \begin{cases} V \times (V - 1), & \text{有向图} \\ \frac{V \times (V - 1)}{2}, & \text{无向图} \end{cases} \]
2、路径🧀
-
迹 (trail)：对于一条途径 \(w\)，若 \(e_1, e_2, \ldots, e_k\) 两两互不相同，则称 \(w\) 是一条迹。
-
路径 (path)（又称 简单路径 (simple path)）：对于一条迹 \(w\)，若其连接的点的序列中点两两不同，则称 \(w\) 是一条路径。
-
环/圈 (cycle)（又称 简单回路/简单环 (simple circuit)）：对于一条回路 \(w\)，若 \(v_0 = v_k\)是点序列中唯一重复出现的点对，则称 \(w\) 是一个环。
3、连接性🧀
- 无向图：连接，对于任意两个顶点，都存在路径相连
- 有向图：强连接，对于任意两个顶点 \(u\)、\(v\)，都存在从 \(u\) 到 \(v\) 和从 \(v\) 到 \(u\) 的路径（适用于有向图）