L002 连通和遍历

连通和 DFS

「路线」（walk）是以顶点开始，顶点和边交替出现，以顶点结束的序列 \(v_0,e_1,v_1,\cdots,e_l,v_l\)，其中每条边 \(e_i\) 的两个端点恰为 \(v_{i-1}\) 和 \(v_i\). 其中 \(v_0\) 和 \(v_l\) 分别称为这条路线的「起点」（starting vertex）和「终点」（ending vertex），这条路线称为一条 \(v_0\)-\(v_l\) 路线，非负整数 \(l\) 称为这条路线的「长度」（length）。

长度为 \(0\) 的路线称为「平凡路线」（trivial walk），其不经过任何边，即序列中仅含一个顶点。

边在序列中不重复出现的路线称为「踪迹」（trail），简称「迹」。顶点在序列中不重复出现的路线称为「路径」（path），简称「路」。

路中除起点和终点外的其他顶点称为「内顶点」（internal vertex）。

在不含重边的简单图中，以两个特定顶点为端点的边唯一，此时序列表示中可省去边而仅记录点。

若图中存在 \(u\)-\(v\) 路，则称顶点 \(u\) 和 \(v\) 「连通」（connected），否则称其「不连通」（disconnected）。

Th.2.1 连通关系是定义在顶点集上的等价关系。

对于图 \(G=\left\langle V,E\right\rangle\)，若 \(V\) 中每对顶点都连通，则称 \(G\) 「连通」（connected），是「连通图」（connected graph）；否则称 \(G\)「不连通」（disconnected），是「不连通图」（disconnected graph）。

图 \(G\) 的极大连通子图称为 \(G\) 的「连通分支」（connected component），极大连通子图即连通的子图但不是任何 \(G\) 连通子图的真子图。阶为 \(1\) 的连通分支称为「平凡连通分支」（trivial connected component）。

「深度优先搜索算法」（DFS 算法, depth-first search algorithm），伪代码如【Algo.2.1】所示。

【Algo.2.1】

Th.2.2 从某顶点出发运行 DFS 算法恰能访问与其连通的所有顶点。

对于阶为 \(n\)，边数为 \(m\) 的图，DFS 算法的时间复杂度是 \(O(n+m)\).

割点与割边

狭义而言，对于连通图 \(G=\left\langle V,E\right\rangle\) 和顶点 \(v\in V\)，图 \(G-v\) 不连通，那么称 \(v\) 为 \(G\) 的「割点」（cut vertex），也称「关节点」（articulation point）。广义而言，对于图 \(G=\left\langle V,E\right\rangle\) 和顶点 \(v\in V\)，若 \(G-v\) 的连通分支数量大于 \(G\) 的连通分支数量，那么称 \(v\) 为 \(G\) 的顶点。

Th.2.3 对于连通图 \(G=\left\langle V,E\right\rangle\) 和顶点 \(v\in V\)，\(v\) 是 \(G\) 的割点当且仅当存在顶点集 \(V\) 的两个不相交非空子集 \(V_i\) 和 \(V_j\)，使得 \(\forall u\in V_i,w\in V_j\)，每条 \(u\)-\(w\) 路都经过 \(v\).

对于图 \(G=\left\langle V,E\right\rangle\) 和边 \(e\in E\)，若图 \(G-e\) 的连通分支数量大于 \(G\) 的连通分支数量，则称 \(e\) 为 \(G\) 的「割边」（cut edge），也称「桥」（bridge）。

Th.2.4 对于连通图 \(G=\left\langle V,E\right\rangle\) 和边 \(e\in E\)，\(e\) 是 \(G\) 的割边当且仅当存在顶点集 \(V\) 的两个不相交非空子集 \(V_i\) 和 \(V_j\)，使得 \(\forall u\in V_i,w\in V_j\)，每条 \(u\)-\(w\) 路都经过 \(e\).

【Algo.2.2】

「父顶点」（parent）、「子顶点」（child）、「根顶点」（root）、「树边」（tree edge）、「后向边」（back edge）、「DFS 树」（DFS tree）、「祖先顶点」（ancestor）、「后代顶点」（descendant）。

Th.2.5 Th.2.6

距离和 BFS

对于顶点 \(u\) 和 \(v\)，长度最小的 \(u\)-\(v\) 路称作 \(u\) 和 \(v\) 间的「最短路」（shortest path）。

顶点 \(u\) 和 \(v\) 间最短路的长度称作 \(u\) 和 \(v\) 间的「距离」（distance），记作 \(\mathrm{dist}(u,v)\)，特别地，若不连通，则定义 \(\mathrm{dist}(u,v)=\infty\).

对于图 \(G=\left\langle V,E\right\rangle\)，距离满足以下性质：：

「非负性」：\(\forall u,v\in V,\mathrm{dist}(u,v)\ge 0\).
「同一性」：\(\mathrm{dist}(u,v)=0\text{ iff. }u=v\).
「对称性」：\(\forall u,v\in V,\mathrm{dist}(u,v)=\mathrm{dist}(v,u)\).
对于连通图 \(G\) 有：「三角不等式」：\(\forall u,v,w\in V,\mathrm{dist}(u,v)+\mathrm{dist}(v,w)\ge \mathrm{dist}(u,w)\).

故而对于连通图 \(G\)，距离是一种「度量」（metric）。度量即满足以上四条性质的函数。

对于图 \(G=\left\langle V,E\right\rangle\)，定义顶点的「离心率」（eccentricity）：

\[ \mathrm{ecc}(v)=\max_{u\in V}\mathrm{dist}(v,u) \]

定义 \(G\) 的「中心点」（central vertex）为 \(V\) 中离心率最小的点，其离心率称为 \(G\) 的「半径」（radius）：

\[ \mathrm{rad}(G)=\min_{u\in V}\mathrm{ecc}(u) \]

\(G\) 所有中心点的集合称为 \(G\) 的「中心」（center）。类似地，称 \(G\) 中离心率最大地点为「边缘点」（peripheral vertex），其离心率称为 \(G\) 的「直径」（diameter）：

\[ \mathrm{diam(G)}=\max_{u\in V}\mathrm{ecc}(u) \]

Th.2.7 对于连通图 \(G\)，有 \(\mathrm{rad}(G)\le \mathrm{diam}(G)\le 2\mathrm{rad}(G)\).

「宽度优先搜索算法」（BFS 算法, breadth-first search algorithm），伪代码如【Algo.2.3】所示。

【Algo.2.3】

「BFS 树」（BFS tree）、「单向搜索」（unidirectional search）、「双向搜索」（bidirectional search）。