L009 有向图

有向图的定义

「有向图」（directed graph）是一个二元组，记作 $G=\left\langle V,A\right\rangle$，其中 $V$ 是顶点的有限集合，$A$ 是「有向边」（directed edge）的有限集合。「有向边」又称「弧」（arc），$A$ 中的每条弧都是一个有序对，由 $V$ 中的两个顶点组成。

对于弧 $a_1=\langle v_1,v_2\rangle$，$v_1$ 和 $v_2$ 分别称为 $a_1$ 的「尾」（tail）和「头」（head），统称为「端点」，弧和其观点互相「关联」。弧是它的头的「入弧」（incoming arc），是它的尾的「出弧」（outgoing arc）。

一条弧的两个端点称作「相邻」，尾是头的「入邻点」（in-neighbor），头是尾的「出邻点」（out-neighbor）。头和尾完全相同的两条弧称作「重弧」（multiple arcs），也称「平行弧」（parallel arcs）。尾和头相反的两条弧互为「反向弧」（inverse arc）。

有向图 $G$ 的顶点数量 $|V|$ 称作 $G$ 的「阶」，记作 $\nu(G)$. $G$ 的弧的数量 $|A|$ 称作 $G$ 的「弧数」（size），记作 $\epsilon(G)$.

顶点 $v$ 关联的入弧的数量称作 $v$ 的「入度」（indegree），记作 $d^-(v)$；关联的出弧的数量称作 $v$ 的「出度」（outdegree），记作 $d^+(v)$；二者之和称为 $v$ 的度，记作 $d(v)$.

Th.7.1 对任意有向图 $G=\left\langle V,A\right\rangle$： $$ \sum_{v\in V} d^-(v)=\sum_{v\in V}d^+(v)=\epsilon(G) $$ Cor.7.1 对任意有向图 $G=\left\langle V,A\right\rangle$： $$ \sum_{v\in V} d(v)=2\epsilon(G) $$ 「入度序列」、「最大入度」、「最小入度」、「出度序列」、「最大出度」、「最小出度」。

将有向图 $G$ 的每条弧（有序对）改为边（无序对）形成的图 $H$ 称为 $G$ 的「底图」（underlying graph），$G$ 称作 $H$ 的「定向」（orientation）。

有向图的表示

邻接矩阵、关联矩阵、邻接表

有向图的连通

有向路线、「起点」和「终点」、长度、有向踪迹/有向迹、有向路径/有向路、有向闭路线、有向闭迹/有向回路、有向圈。

对于有向图 $G=\left\langle V,A\right\rangle$，若 $G$ 的底图连通，则称 $G$「弱连通」（weakly connected），是「弱连通图」（weakly connected graph）。若有向图中存在 $u$-$v$ 有向路，那么称 $v$ 是从 $u$「可达」的（reachable）。若有向图 $G=\left\langle V,A\right\rangle$ 中每对顶点都相互可达，则称 $G$「强连通」（strongly connected），是「强连通图」（strongly connected graph）。

Th.7.2 对于有向图 $G=\left\langle V,A\right\rangle$，其强连通当且仅当 $G$ 存在一条有向闭路线经过 $V$ 中所有顶点。

Th.7.3（Robbins 定理）：连通图 $G$ 有强连通定向当且仅当 $G$ 没有割边。

有向图 $G$ 的极大弱连通子图称为 $G$ 的「弱连通分支」（weakly connected component），$G$ 的极大强连通子图称为 $G$ 的「强连通分支」（strongly connected component）。

顶点集 $V$ 上的互相可达关系将 $V$ 划分为若干子集，每个子集的点导出子图形成一个强连通分支。

将有向图 $G$ 的所有强连通分支的集合记为 $C$，构造有向图 $H=\left\langle C,A'\right\rangle$，每个顶点 $c_i\in C$ 表示 $G$ 的一个强连通分支，弧 $\langle c_i,c_j\rangle\in A'$ 当且仅当 $G$ 含一条弧，其尾和头分别在 $c_i$ 和 $c_j$ 表示的强连通分支中。$H$ 称作 $G$ 的「浓缩」（condensation）。

【Algo.7.1】

「塔尔真强连通分支算法」（Tarjan's strongly connected components algorithm）

【Algo.7.2】

Th.7.4 Th.7.5

有向图的距离

在有向图中，对于顶点 $u$ 和 $v$，长度最小的 $u$-$v$ 有向路称为从 $u$ 到 $v$ 的「最短有向路」（shortest directed path），其长度称为 $u$ 到 $v$ 的「距离」，记作 $\mathrm{dist}(u,v)$，特别地若不可达，则定义 $\mathrm{dist}(u,v)=\infty$.