第九章 有向图

9.1 有向图及其连通性

有向图的概念与性质

有向图

一个有向图 $D$ (digraph) 是指一个三元组 $(V(D),E(D),{ф}_D)$. 其中, $V(D)$ 是非空的顶点集合, $E(D)$ 是不与 $V(D)$ 相交的边集合, 而 ${ф}_D$ 是关联函数, 它使 $D$ 的每条边对应 $D$ 的有序顶点对 (不必相异).

弧

如果 $e$ 是 $D$ 的一条边, 而 $u$ 与 $v$ 是使得 ${ф}_D(u,v)=e$ 的顶点, 那么称 $e$ 是由 $u$ 连接到 $v$, 记为 $e=(u,v)$. 同时, 称 $u$ 为 $e$ 的弧尾 (起点, tail), $v$ 为 $e$ 的弧头 (终点, head).

注: 有向图可以简单地理解为 “边有方向的图”.

平行边 重数

在一个有向图 $D$ 中, 具有相同起点和终点的边称为平行边 (multiple edge). 两点间平行边的条数称为该两点间的重数 (multiplicity).

简单有向图

在一个有向图 $D$ 中, 如果没有有向自环和平行边, 则称该图为简单有向图 (simple digraph).

有向图的基础图, 无向图的定向图

设 $D$ 是有向图, 去掉 $D$ 中边的方向后得到的无向图 $G$, 称为 $D$ 的基础图.

又若 $G$ 是无向图, 给 $G$ 的每条边加上方向后得到的有向图 $D$ 称为 $G$ 的一个定向图 (oriented graph).

例

一个简单图有多少个定向图？

解: 因为每条边有 $2$ 种定向方式, 所以共有 $2^{m(G)}$ 种定向.

出度 $d^{+}(v)$, 入度 $d^{-}(v)$, 度 $d(v)$

设 $D$ 是有向图, $v$ 是 $D$ 中顶点.

以 $v$ 为始点的边的条数称为点 $v$ 的出度 (out-degree), 以 $v$ 为端点的一个自环算 $1$ 度. 点 $v$ 的出度记为 $d^{+}(v)$;
以 $v$ 为终点的边的条数称为点 $v$ 的入度 (in-degree), 以 $v$ 为端点的一个自环算 $1$ 度. 点 $v$ 的入度记为 $d^{-}(v)$;

点 $v$ 的出度与入度之和称为点 $v$ 的度, 记为 $d(v)$.

例

求证: 存在一个 $G$ 的定向图 $D$, 使得对 $\forall v\in V(D)$, 有 $|d^{+}(v)-d^{-}(v)|\le 1$.

证明:

不失一般性, 设 $G$ 是连通图. $G$ 中奇度顶点个数必然为偶数个, 将偶数个奇数度顶点配对, 然后在每一对配对顶点间连一条边得到欧拉图 $G_1$.

在 $G_1$ 中用 Fleury 算法求出 $G$ 的一个欧拉环游 $C$, 然后顺次地在 $C$ 上标上方向, 由此得到 $C$ 的定向图 $C_1$.

在 $C_1$ 中, 去掉添加的边后, 得到 $G$ 的定向图 $D$.

显然: 对 $\forall v\in V(D)$, 有 $|d^{+}(v)-d^{-}(v)|\le 1$.

定理

设 $D=(V,E)$ 是有向图, 则:

$$\sum _{v=V(D)}{d}^{+}(v)=\sum _{v\in V(D)}{d}^{-}(v)=m(D)$$

证明: 由出度与入度的定义立即可得上面等式.

有向图的矩阵表示

设 $D=(V,E)$ 是有向图, 其中 $V=\{v_1,v_2,\dots ,v_n\},E=\{e_1,e_2,\dots ,e_m\}$.

邻接矩阵 $A$

称 $A(D)=(a_{ij}{)}_{n\times n}$ 是 $D$ 的邻接矩阵, 其中 $a_{ij}$ 是 $v_i$ 为起点, $v_j$ 为终点的边的条数, $1\le i\le n,1\le j\le n$.

注: 有向图的邻接矩阵不一定对称.

关联矩阵 $M$

若 $D$ 无自环. 称矩阵 $M=(m_{ij}{)}_{n\times m}$ 是 $D$ 的关联矩阵, 其中

$$m_{ij}=\{\begin{array}{ll}1,& v_i是e_j的起点\\ -1,& v_i是边e_j的终点(1\le i\le n,1\le j\le m)\\ 0,& 其它\end{array}$$

关联矩阵 $M$ 的性质

$M{M}^T=D(G)-A(G)$, 其中 $D$ 是对应无向图的度矩阵, $A$ 是对应无向图的邻接矩阵.

例

写出下面有向图 $D_1$ 的邻接矩阵和 $D_2$ 的关联矩阵.

$$A(D_1)=\left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 2& 1& 2\\ 0& 0& 0& 0\\ 0& 0& 1& 0\end{array}\right)M(D_2)=\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ -1& 1& -1& 1& 0\\ 0& -1& 1& 0& 1\\ 0& 0& 0& -1& -1\end{array}\right)$$

有向图的连通性

有向途径 (闭途径)、迹 (闭迹) 和路 (圈)

上面概念与无向图中相关概念类似.

有向图中顶点间的连通性

设 $D=(V,E)$ 是有向图, $u$ 与 $v$ 是 $D$ 中两个顶点.

1. 若 $D$ 中存在一条 $(u,v)$ 路, 则称 $u$ 可达 $v$ , 记为 $u\to v$ . 规定 $u\to u$ .
2. 若 $D$ 中存在一条 $(u,v)$ 路或 $(v,u)$ 路, 则称 $u$ 与 $v$ 是单向连通的.
3. 若 $D$ 中存在一条 $(u,v)$ 路和一条 $(v,u)$ 路, 则称 $u$ 与 $v$ 是双向连通的或强连通的 (strongly connected).

★弱连通图, 单向连通图, 强连通图

设 $D=(V,E)$ 是有向图.

1. 若 $D$ 的基础图是连通的, 称 $D$ 是弱连通图 (weakly connected);
2. 若 $D$ 的中任意两点是单向连通的, 称 $D$ 是单向连通图 (unilaterally connected);
3. 若 $D$ 的中任意两点是双向连通的, 称 $D$ 是强连通图 (strongly connected).

在上面三图中, $D_1$ 仅为弱连通图, $D_2$ 是单向连通的, 而 $D_3$ 是强连通的.

定理

有向图 $D=(V,E)$ 是强连通的, 当且仅当 $D$ 中存在包含 $D$ 中所有顶点的回路.

证明:

“必要性”

设 $V(D)=\{v_1,v_2,\dots ,v_n\}$. 由于 $D$ 是强连通图, 所以, 对任意两点 $v_i$ 与 $v_j$, 都存在 $(v_i,v_j)$ 路, 同时也存在 $(v_j,v_i)$ 路. 所以存在如下闭途径: $v_1\to v_2\to \dots \to v_n\to v_1$. 这是一条包含 $D$ 的所有顶点的回路.

“充分性”

不失一般性, 设 $C=v_1\to v_2\to \dots \to v_n\to v_1$ 是包含 $D$ 的所有顶点的一条回路. 对于 $D$ 的任意两点 $v_i$ 与 $v_j$, 一方面, 由 $C$ 可得到 $v_i$ 到 $v_j$ 的途径 $v_i\to v_{i+1}\to \dots \to v_j$. 另一方面, 由 $C$ 又可得到 $v_j$ 到 $v_i$ 的途径 $v_j\to v_{j+1}\to \dots v_{i-1}\to v_i$. 所以 $D$ 中任意两点是强连通的, 即 $D$ 是强连通图.

例

说明下图 $D$ 是强连通图.

解: $v_1{v}_5{v}_6{v}_2{v}_4{v}_3{v}_2{v}_4{v}_5{v}_6{v}_2{v}_1$ 是含 $D$ 所有顶点的一条回路.

强连通分支, 单向连通分支, 弱连通分支

设 $D’$ 是有向图 $D=(V,E)$ 的一个子图. 如果 $D’$ 是强连通的 (单向连通的、弱连通的), 且 $D$ 中不存在真包含 $D’$ 的子图是强连通的 (单向连通的、弱连通的), 则称 $D’$ 是 $D$ 的一个强连通分支 (单向连通分支、弱连通分支).

例

求下图 $D$ 的强连通分支、单向连通分支.

(1) $D$ 的强连通分支

$\{1\}\{2,3,9,8,4,7\}\{5\}\{6\}$

上面点集导出的子图是 $D$ 的强连通分支.

(2) $D$ 的单向连通分支

$D$ 的单向连通分支就是 $D$ 本身.

注: 求 $D$ 的强、弱连通分支比较容易, 求单向分支比较困难.

定理

有向图 $D=(V,E)$ 的每个点均位于 $D$ 中唯一的强 (弱) 连通分支中.

证明: 对于弱连通分支情形, 命题结论是显然的.

对于强连通分支情形, 因为不难证明: $D$ 中顶点间的强连通关系是等价关系. 该等价关系对应的等价类在 $D$ 中的导出子图必然是 $D$ 的一个强连通分支. 而 $D$ 的一个强连通分支包含的顶点也必然是该等价关系的一个等价类.

但是, 对于单向连通分支来说, $D$ 的某个顶点, 可能会分属于 $D$ 的若干个单向连通分支. 原因是单向连通关系不是等价关系.

9.2 图的定向问题

图的定向问题是有向图中的一个典型问题之一, 具有广泛的应用背景.

城市交通网设计问题: 一座城市为某种需要, 要把所有街道改为单行道, 使得人们在任意两个位置都可以相互到达. 如何设计单行道方向？图论建模: 街道交叉口模型为图的顶点, 两点连线当且仅当该两点是某街道的端点. 问题等价于在模型图中给出其强连通定向.

对于任意一个无环图 $G$, 要对其作强连通定向, 需要解决两个问题: 一是强连通定向的存在性问题, 二是如何定向问题. 上面两个问题都已经得到解决.

定理: 强连通定向的存在性问题

(Robbins, 1939) 非平凡连通图 $G$ 具有强连通定向当且仅当 $G$ 是 $2$ 边连通的.

强连通定向算法

该算法采用顶点标号方法给边标上方向. 设 $G=(V,E)$ 是 $2$ 边连通图.

(1) 在 $G$ 中任取顶点 $w$, 令 $l(w)=1,L=\{w\},U=V-\{w\},A=\Phi$;

(2) 在 $L$ 中找 $l(v)$ 最大的点 $v$, 同时 $v$ 在 $U$ 中存在邻点 $u$. 然后作有向边 $(v,u)$. 令 $l(u)=l(v)+1,L=L\cup u,U=U-u$ 且 $A=A\cup (v,u)$; (注: 标号从小到大的有向边)

(3) 若 $L\ne V$, 转 (2); 否则转 (4);

(4) 对剩下的未赋予方向的边, 按由标号值大的顶点指向标号值小的顶点赋予方向.

例

求下图 $G$ 的强连通定向.

解:

(1) 取点 $v_1$, 令 $l(v_1)=1,L=\{v_1\},U=\{v_2,v_3,\dots ,v_7\},A=\Phi$;

(2) 在 $U$ 中取点 $v_7$, 作边 $(v_1,v_7)$. 令 $l(v_7)=l(v_1)+1=2$,

$L=\{v_1,v_7\},U=\{v_2,v_3,\dots ,v_6\},A=\{(v_1,v_7)\}$;

(2) 在 $L$ 中取 $v_7$, $U$ 中取点 $v_6$ , 作边 $(v_7,v_6)$. 令 $l(v_6)=l(v_7)+1=3$,

$L=\{v_1,v_7,v_6\},U=\{v_2,v_3,\dots ,v_5\},A=\{(v_1,v_7),(v_7,v_6)\}$;

(2) 在 $L$ 中取 $v_6$, $U$ 中取点 $v_5$, 作边 $(v_6,v_5)$. 令 $l(v_5)=l(v_6)+1=4$,

$L=\{v_1,v_7,v_6,v_5\},U=\{v_2,v_3,v_4\},A=\{(v_1,v_7),(v_7,v_6),(v_6,v_5)\}$;

(2) 在 $L$ 中取 $v_5$, $U$ 中取点 $v_2$ , 作边 $(v_5,v_2)$. 令 $l(v_2)=l(v_5)+1=5$,

$L=\{v_1,v_7,v_6,v_5,v_2\},U=\{v_3,v_4\},A=\{(v_1,v_7),(v_7,v_6),(v_6,v_5),(v_5,v_2)\}$;

(2) 在 $L$ 中取 $v_2$, $U$ 中取点 $v_3$, 作边 $(v_2,v_3)$. 令 $l(v_3)=l(v_2)+1=6$,

$L=\{v_1,v_7,v_6,v_5,v_2,v_3\},U=\{v_4\},A=\{(v_1,v_7),(v_7,v_6),(v_6,v_5),(v_5,v_2),(v_2,v_3)\}$;

(2) 在 $L$ 中取 $v_3$, $U$ 中取点 $v_4$, 作边 $(v_3,v_4)$. 令 $l(v_4)=l(v_3)+1=7$,

$L=\{v_1,v_7,v_6,v_5,v_2,v_3,v_4\},U=\Phi ,A=\{(v_1,v_7),(v_7,v_6),(v_6,v_5),(v_5,v_2),(v_2,v_3),(v_3,v_4)\}$;

(3) $U=\Phi$, 所以, 由 (4) , 对剩下的边赋予方向.

9.3 有向路与有向圈

定理: 有向圈的存在性

设 $D=(V,E)$ 是有向图.

(1) 若 $D$ 中对任意的 $v\in V(D)$ 均有 $d^{+}(v)>0$ (或 $d^{-}(v)>0)$, 则 $D$ 中存在有向圈.

(2) 若 $D$ 连通, 且对任意的 $v\in V(D)$ 均有 $d^{+}(v)=1$ (或 $d^{-}(v)=1$), 则 $D$ 中存在唯一有向圈.

定理: 有向欧拉环游的存在性

设 $D=(V,E)$ 是有向图. $D$ 中存在有向欧拉环游, 当且仅当 $D$ 连通且每个点的出度和入度相等;

思考: 有向图 $D$ 中存在有向欧拉迹的充要条件?

竞赛图

在各种比赛中, 循环赛是常见形式, 即对与对各队之间都要进行比赛. 循环赛的结果可用所谓的 “竞赛图” (tournament) 来表示. 若 $u$ 队战胜了 $v$ 队, 则由点 $u$ 向 $v$ 画一条有向边.

显然, “竞赛图” 是完全图的一种定向图.

定理

$n$ 阶完全图的定向方式有 $2^{\frac{n(n-1)}{2}}$ 种.

从同构的意义上看: 一阶竞赛图有 $1$ 个; 二阶竞赛图有 $1$ 个; 三阶竞赛图有 $2$ 个; 四阶竞赛图有 $4$ 个; 五阶竞赛图有 $12$ 个. $12$ 阶竞赛图超过 $1540$ 亿个.

定理 (Rédei, 1934)

竞赛图中存在有向 $H$ 路.

定理 (Camion, 1959)

强连通竞赛图中存在有向 $H$ 圈.

有向图的相关结论, 可参考 Jørgen Bang-Jensen, Gregory Z. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, London, 2009.