Deed's Burial - 离散数学笔记-图论

Disclaimer

some parts were auto-completed by copilot, since I am a worn-out lazy heck, and never appeared to manage time properly.

Summary

图的基本概念
1. 图
2. 通路与回路
3. 图的连通性
4. 图的矩阵表示
欧拉图与汉密尔顿图
树
平面图

一. 图的基本概念

1) 图

图是由顶点和边组成的数学结构，用于表示对象之间的关系。图可以是有向的或无向的，边可以带权重或不带权重。
对于有向图或无向图，均用二元组 $⟨ V, E ⟩$ 表示，其中 $V$ 为顶点集合， $E$ 为边集合。
其中，对于边，无向边使用 $(v_{1}, v_{2})$ 表示，其中 $v_{1}$ 与 $v_{2}$ 为两个端点，顺序可调换；
有向边使用笛卡尔积 $V \times V$ 表示，即 $⟨ v_{1}, v_{2} ⟩$ ，其中 $v_{1}$ 与 $v_{2}$ 表示从 $v_{1}$ 指向 $v_{2}$ 的矢量，顺序不可调换。
图的阶，指图中顶点的个数。 $n$ 个顶点的图即称作 $n$ 阶图。
（零图：没有边的图；平凡图：1阶零图）
无向图的关联和相邻：如图G1所示。
- 关联：
  对于边 $e_{1} = (v_{1}, v_{2})$ ，称 $v_{1}$ 、 $v_{2}$ 与 $e_{1}$ 相关联，且由于 $v_{1}$ 与 $v_{2}$ 不相同，关联次数为1。
  假设一自反关系 $e_{2} = (v_{1}, v_{1})$ 定义在图G1上，则称 $e_{2}$ 与 $v_{1}$ 相关联，且关联次数为2。同理， $e_{2}$ 与 $v_{2}$ 的关联次数为0，即不关联。
- 相邻：
  对于任意有公共边的点，如 $v_{1}$ 、 $v_{2}$ 或 $v_{3}$ 、 $v_{4}$ ，称它们相邻。
  对于任意有公共端点的边，如 $e_{1}$ 、 $e_{3}$ 或 $e_{4}$ 、 $e_{5}$ ，称它们相邻。

graph subgraph G1 direction LR v1((v1)) v2((v2)) v3((v3)) v4((v4)) v5((v5)) v1 ---|e1| v2 v1 ---|e2| v1 v1 ---|e3| v2 v1 ---|e4| v3 v3 ---|e5| v4 end

有向图的端点、关联和相邻：如图D1所示。
- 端点：对于有向边 $e_{1} = ⟨ v_{1}, v_{2} ⟩$ ，称 $v_{1}$ 为始点， $v_{2}$ 为终点。
- 关联和相邻原理与无向图同理。

graph subgraph D1 direction LR v1((v1)) v2((v2)) v3((v3)) v4((v4)) v1 -->|e1| v2 v4 -->|e2| v1 v2 -->|e3| v4 v4 -->|e4| v2 v2 -->|e5| v3 end

无向图的度数（度）：顶点 $v$ 作为无向边的端点的次数，记作 $d (v)$ 。
- 如图G1， $d (v_{2}) = 2$ , $d (v_{1}) = 5$
有向图的度数：
- 入度：顶点 $v$ 作为有向边的终点的次数，记作 $d^{-} (v)$
- 出度：顶点 $v$ 作为有向边的始点的次数，记作 $d^{+} (v)$
  （ $d (v) = d^{+} (v) + d^{-} (v)$ ）
- 如图D2，
  $∵ ∴ ∵ ∴ d^{+} (v_{2}) = 1 d^{-} (v_{2}) = 2 d (v_{2}) = d^{+} (v_{2}) + d^{-} (v_{2}) = 3 d^{+} (v_{4}) = 2 d^{-} (v_{4}) = 2 d (v_{4}) = d^{+} (v_{4}) + d^{-} (v_{4}) = 4$

graph subgraph D2 direction LR v1((v1)) v2((v2)) v3((v3)) v4((v4)) v1 --> v2 & v2 & v3 v2 --> v3 v3 --> v4 v4 --> v4 & v3 end

握手定理：
- 无向图： $\sum_{v \in V} d (v) = 2∣ E ∣$
- 有向图：
  - $\sum_{v \in V} d (v) = 2∣ E ∣$
  - $\sum_{v \in V} d^{-} (v) = \sum_{v \in V} d^{+} (v) = ∣ E ∣$
- 推论:
  - 任何图中，奇度顶点的个数是偶数
    （原因：每条边都会贡献两次度数，因此所有度数的和必为偶数，所以奇度顶点的个数必须是偶数，否则矛盾）
  - $\sum_{v \in V} d (v_{o dd})$ + $\sum_{v \in V} d (v_{e v e n})$ = $\sum_{v \in V} d (v)$
- e.g
  已知 $n$ 阶无向图 $G$ 中有 $m$ 条边，各个顶点的度数均为 $3$ ，又已知 $2 n - 3 = m$ , 则 $m = 9$
  解析：
  $∵ ∴ 3 n = 2 m 2 n - 3 = m 4 n - 6 = 2 m m = 9$
度数列：
- $n$ 阶无向图：
  $d (v_{1}), d (v_{2}), \dots, d (v_{n}) d = (d_{1}, d_{2}, \dots, d_{n})$
- $n$ 阶有向图：
  - 入度列：
    $d^{-} (v_{1}), d^{-} (v_{2}), \dots, d^{-} (v_{n}) d^{-} = (d_{1}^{-}, d_{2}^{-}, \dots, d_{n}^{-})$
  - 出度列：
    $d^{+} (v_{1}), d^{+} (v_{2}), \dots, d^{+} (v_{n}) d^{+} = (d_{1}^{+}, d_{2}^{+}, \dots, d_{n}^{+})$
- e.g.
  - 一个三阶有向图的度序列是 $2, 2, 4$ ，入度序列是 $2, 0, 2$ ，则出度序列是 $0, 2, 2$
- 非负整数列 $d = (d_{1}, d_{2}, \dots d_{n})$ 是可图化的，当且仅当 $\sum_{i = 1}^{n} d_{i}$ 为偶数；
- 非负整数列 $d = (d_{1}, d_{2}, \dots d_{n})$ 是简单可图化的，当且仅当：
  - 1. $\sum_{i = 1}^{n} d_{i}$ 为偶数
  - 2. $d (v_{i}) \leq n - 1$
    即 $Δ (G) \leq n - 1$
    （注：最大度 $Δ (G)$ ，最小度 $δ (G)$ ）
无向完全图：设 $G$ 为 $n$ 阶无向简单图，若 $G$ 中每个顶点均与其余的 $n - 1$ 个顶点相邻，则称 $G$ 为无向完全图，记作 $K_{n}$ 。
$n$ 阶无向完全图 $K_{n} (n \geq 1)$ 的边的条数为 $\frac{n ( n - 1 )}{2}$

2) 通路与回路

通路：对于无向图中G中的顶点与边的交替序列 $Γ = v_{i_{0}} e_{j_{1}} v_{i_{1}} e_{j_{2}} v_{i_{2}} \dots e_{j_{k}} v_{i_{k}}$ ，若 $v_{i_{0}} = v_{j_{k}}$ ，则称 $Γ$ 为回路。
对于图 $G 1$ ， $Γ_{1} = v_{1} e_{2} v_{3} e_{4}$ 是一个回路。

3) 图的连通性

设无向图 $G = ⟨ V, E ⟩$ ，若 $u, v \in V$ 之间存在通路，则称 $u, v$ 是连通的，记作 $u \sim v$
若无向图 $G$ 是平凡图或 $G$ 中任意两个顶点都是连通的，则称 $G$ 是连通图。
在有向图 $G = ⟨ V, E ⟩$ 中，对于 $u, v \in V$ ，若从 $u$ 到 $v$ 存在通路，则称 $u$ 到 $v$ 可达，记作 $u \to v$ 。若在此基础上，从 $v$ 到 $u$ 也存在通路，则称 $u ， v$ 是相互可达的。规定 $\forall u \in V, u \to u$ 。
对于有向图 $G = ⟨ V, E ⟩$ ：
- 强连通图： $\forall u, v \in V, u \to v \land v \to u$
- 单向连通图: $\forall u, v \in V, u \to v \lor v \to u$
- 弱连通图: 在略去有向边后得到的无向图是连通的。

4) 图的矩阵表示

对于无向图 $G = ⟨ V, E ⟩, V = {v_{1}, v_{2}, \dots, v_{n}}, E = {e_{1}, e_{2}, \dots, e_{m}}$ , 令 $m_{ij}$ 为 $v_{i}$ 和 $v_{j}$ 之间的边的条数，则称矩阵 $M = [m_{ij}]_{n \times n}$ 为图 $G$ 的关联矩阵。

<aigc>

其他常用的图的矩阵表示：
- 邻接矩阵(Adjacency matrix)：对于简单无向图 $G$ ，定义 $A = [a_{ij}]_{n \times n}$ ，其中 a{ij}=\begin{cases}1,&\text{若 }(vi,v_j)\in E\0,&\text{否则}\end{cases} 对于有向图， $A$ 为非对称矩阵；对于带权图， $a_{ij}$ 可取为对应边的权值。
- 关联矩阵(Incidence matrix)：对于无向图 $G$ ，令 $B = [b_{ij}]_{n \times m}$ ，顶点为行、边为列，若边 $e_{j}$ 与顶点 $v_{i}$ 关联则 $b_{ij} = 1$ （环可计为2），否则为0。对于有向图可将入、出端用-1、+1标记。
- 度矩阵(Degree matrix)：对角矩阵 $D = diag (d (v_{1}), \dots, d (v_{n}))$ ，常与邻接矩阵一起用于构造拉普拉斯矩阵。
- 拉普拉斯矩阵(Graph Laplacian)：定义为 $L = D - A$ ，其中 $D$ 为度矩阵， $A$ 为邻接矩阵。 $L$ 为对称半正定矩阵，零特征值的重数等于连通分支数，可用于研究图的谱性质、连通性与随机游走。
- 归一化拉普拉斯矩阵(Normalized Laplacian)：一种常用形式为 $L = D^{- 1/2} L D^{- 1/2} = I - D^{- 1/2} A D^{- 1/2}$ ，便于处理度异质性的图谱分析。
这些矩阵在图论的算法与谱图理论中广泛使用，用于表示结构、计算最短路、连通分量、谱聚类等。

</aigc>

二. 欧拉图与汉密尔顿哈密顿图

1) 欧拉图

欧拉通路：通过图中所有边一次，且仅通过一次的通路。
欧拉回路：定义相同的回路
欧拉图：具有欧拉回路的图
半欧拉图：具有欧拉通路但不具有欧拉回路的图
- 无向图 $G$ 是欧拉图，当且仅当 $G$ 是连通图且 $\forall v \in V, d (v)$ 为偶数
- 有向图 $D$ 是欧拉图，当且仅当D为强连通图，且 $\forall v \in V, d^{+} (v) = d^{-} (v)$
2) 哈密顿图
哈密顿通路：经过图中所有顶点一次，且仅经过一次的通路。
哈密顿回路：定义相同的回路
哈密顿图：具有哈密顿回路的图
半哈密顿图：具有哈密顿通路但不具有哈密顿回路的图
- 充分条件：
  - 设 $G$ 是 $n$ 阶无向简单图，若 $\forall u, v \in V, \neg (u \sim v) \land d (u) + d (v) \geq n - 1$ , 则G中存在哈密顿通路
  - 设 $G$ 是 $n (n \geq 3)$ 阶简单无向图，若 $\forall u, v \in V, \neg (u \sim v) \land d (u) + d (v) \geq n$ ，则 $G$ 中存在哈密顿回路

3) 最短路问题

权和带权图：

graph subgraph W1 direction LR v1((v1)) v2((v2)) v3((v3)) v4((v4)) v5((v5)) v6((v6)) v1 ---|1| v2 v3 ---|1| v5 v2 ---|2| v3 v4 ---|2| v6 v4 ---|3| v5 v1 ---|4| v3 v2 ---|5| v5 v5 ---|6| v6 v2 ---|7| v4 end

称图 $G = ⟨ V, E, W ⟩$ 为带权图，其中 $W$ 为权集， $W = {w_{1}, w_{2}, \dots, w_{m}}$ ， $w_{i}$ 为边 $e_{i}$ 的权值。
最短路径：在带权图中， $\forall u, v \in V$ ， $u \sim v$ 时，从 $u$ 到 $v$ 长度 $($ 权的和 $)$ 最短的路径，称其长度为从 $u$ 到 $v$ 的距离，记作 $d (u, v)$ 。
规定：
- $d (u, u) = 0$
- $\neg (u \sim v) \Rightarrow d (u, v) = + \infty$
最短路问题：在带权图中，求 $\forall u, v \in V$ ， $u \sim v$ 时，从 $u$ 到 $v$ 的最短路径。

计算方法：Dijkstra算法

算法思想：

初始化：设定起点 $s$ ，将 $s$ 加入已确定最短路径的集合 $S$ ，并将所有顶点的距离 $d (v)$ 初始化为 $\infty$ ，除了 $d (s) = 0$ 。
迭代：

* 从未确定的顶点中选择距离最小的顶点<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">u</span></span></span></span>，将其加入集合<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.0576em;">S</span></span></span></span>。  
（第一次选择也就是加入<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">s</span></span></span></span>）
* 对于每个与<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">u</span></span></span></span>相邻的顶点<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.0359em;">v</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel"><span class="mord"><span class="mrel">∈</span></span><span class="mord vbox"><span class="thinbox"><span class="llap"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="inner"><span class="mord"><span class="mord">/</span><span class="mspace" style="margin-right:0.0556em;"></span></span></span><span class="fix"></span></span></span></span></span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.0576em;">S</span></span></span></span>，检查是否可以通过<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">u</span></span></span></span>更新<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">d</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.0359em;">v</span><span class="mclose">)</span></span></span></span>：
  <span class="katex-display"><span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">d</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.0359em;">v</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mop">min</span><span class="mopen">(</span><span class="mord mathnormal">d</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.0359em;">v</span><span class="mclose">)</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal">d</span><span class="mopen">(</span><span class="mord mathnormal">u</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.0269em;">w</span><span class="mopen">(</span><span class="mord mathnormal">u</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.0359em;">v</span><span class="mclose">))</span></span></span></span></span>

重复步骤2，直到所有顶点都被加入集合 $S$ 或所有可达顶点的最短路径已确定。

（其实我也不知道怎么描述，以上是aigc）

得，写不完了，让我拖完了，只能说f1太好看了。

离散数学笔记-图论

Summary

一. 图的基本概念

二. 欧拉图与 汉密尔顿 哈密顿图

二. 欧拉图与汉密尔顿哈密顿图