Graph Theory and Network Algorithm 7 有向图
图论与网络算法 (070105M04003H)，有向图。
有向图
概念
- 有向图（digraph, directed graph）：每条边都具有一个方向的图。
- 出度：从\(v\)出发的弧的数目，记为\(d^{+}_{\vec{G}}(v)\)；入度：指向\(v\)的弧的数目，记为\(d^{-}_{\vec{G}}(v)\)；
- 出度、入度之和称为度，即\(d(v)=d^{+}_{\vec{G}}(v)+d^{-}_{\vec{G}}(v)\)。
- 有向途径
- 有向迹
- 有向路
- 有向圈
- 弱连通图：底图为连通图的有向图。
- 单连通图：\(\forall u,v\in v(G):\exists P(u,v)\ |\ P(v,u)\)。
- 强连通图：\(\forall u,v\in v(G):\exists P(u,v)\ \&\ P(v,u)\)。
强连通图\(\Longrightarrow\)单连通图\(\Longrightarrow\)弱连通图
- Euler有向迹
- Euler有向闭迹
- Euler有向图：存在Euler有向闭迹的图。
- Hamilton有向路
- Hamilton有向圈
- Hamilton有向图：存在Hamilton有向圈的图。
- 竞赛图：定向完全图。
- 王：竞赛图中到任何其他顶点都有长不超过\(2\)有向路的顶点。
若\(v\)是王，则所有其他选手要么直接败给了\(v\)，要么败给了\(v\)的手下败将。
定理
设\(A'\)为使有向图\(\vec{G}-A'\)不含有向圈的最小弧子集，设\(\vec{G}-A'\)中最长有向路的长为\(k\)。按如下方式将颜色\(1,2,...,k+1\)分配给\(\vec{G}-A'\)的顶点：$\forall v\in V(\vec{G}-A')$，若$\vec{G}-A'$从$v$出发的最长有向路为$i$，则给$v$染色$i+1$，可证该染色是\(G\)的正常\(k+1\)顶点染色，故\(\chi(G)\le k+1\)，即\(k\ge\chi(G)-1\)。
再证明竞赛图有Hamilton有向路时会用到。
竞赛图证明王的存在性要用到。
\(\Longrightarrow\) 显然；
\(\Longleftarrow\) 逐步构造圈。
仅需证唯一性，反证，分三类讨论：两圈有公共弧；无公共弧但有公共顶点；无公共顶点。
易证。
- (Woodall, 1973) 非平凡简单有向图\(\vec{G}\)，若\(\forall u,v\in V(\vec{G}):<u,v>\notin A(\vec{G}),d^{+}(u)+d^{-}(v)\ge \upsilon \Longrightarrow \vec{G}\)是Hamilton有向图。
先证强连通，再用Theorem 8.4.4。
- (Ghouilà-Houri, 1960) 强连通简单有向图\(\vec{G},\forall v\in V(\vec{G}):d(v)\ge\upsilon\Longrightarrow \vec{G}\)是Hamilton有向图。
- (Ghouilà-Houri, 1960) 简单有向图\(\vec{G},\forall v\in V(\vec{G}):d^{+}(v)\ge\frac{\upsilon}{2},d^{-}(v)\ge\frac{\upsilon}{2}\Longrightarrow \vec{G}\)是Hamilton有向图。
添加一点，并和其余顶点都连上两条方向相反得弧，得到一个强连通图，再用Theorem 8.4.4。
- 非平凡简单有向图\(\vec{G}\)，若\(\forall u,v\in V(\vec{G}):<u,v>\notin A(\vec{G}),d^{+}(u)+d^{-}(v)\ge \upsilon-1 \Longrightarrow \vec{G}\)有Hamilton有向路。
- 简单有向图\(\vec{G},\forall v\in V(\vec{G}):d(v)\ge\upsilon-1\Longrightarrow \vec{G}\)有Hamilton有向路。
- 简单有向图\(\vec{G},\forall v\in V(\vec{G}):d^{+}(v)\ge\frac{\upsilon-1}{2},d^{-}(v)\ge\frac{\upsilon-1}{2}\Longrightarrow \vec{G}\)有Hamilton有向路。
完全图的任何独立集都只含一个顶点，由Theorem 8.2.2结论成立。
设出该点的出入邻点，按王的定义证明（到这些顶点都有长不超过\(2\)的有向路）。
得胜多的必为王，但反之不真；
王未必唯一。
\(\Longrightarrow\) 反证，若存在入邻点，则该点入邻点的导出子图有王，且是原图的王，矛盾。
\(\Longleftarrow\) 反证，若不唯一，则\(v\)的入度至少为\(1\)，矛盾。
由Theorem 8.2.1，竞赛图有长为\(\chi-1=\upsilon-1\)的有向路，即为Hamilton有向路。
非常强的定理；
泛圈性：一个图含有长为\(3,4,...,\upsilon\)的圈；
强连通竞赛图具有泛圈性。
- (Camion, 1959) 强连通竞赛图时Hamilton有向图。
算法
求强连通定向图
- Hopcroft-Tarjan定向算法
- 思想：从任一点出发，按照树的生长过程（深度优先）生长出一颗有向生成树\(\vec{T}\)，然后对每条不在\(\vec{T}\)的边，按顶点进入\(\vec{T}\)的顺序由后向前定向。
- 复杂度：\(O(\upsilon^2)\)
练习
- 设\(n\)名棋手进行循环赛\((n\ge3)\)，没有出现平局。证明：若不出现甲胜乙、乙胜丙、丙又胜甲的情况，则必有一人再所有比赛中全胜，也必有一人再所有比赛中全败。
先证该竞赛图无圈，再取最长路，端点即为全胜和全败的人。
- 证明每个竞赛图都有\(\sum\limits_{v\in V}[d^{+}(v)]^2=\sum\limits_{v\in V}[d^{-}(v)]^2\)
\(\sum_{v \in V}\left[d^{+}(v)\right]^{2}-\sum_{v \in V}\left[d^{-}(v)\right]^{2}=\sum_{v \in V}\left\{\left[d^{+}(v)\right]^{2}-\left[d^{-}(v)\right]^{2}\right\}\) \(=\sum_{v \in V}\left[\left(d^{+}(v)+d^{-}(v)\right) \cdot\left(d^{+}(v)-d^{-}(v)\right)\right]\) \(=(v-1) \sum_{v \in V}\left(d^{+}(v)-d^{-}(v)\right)\) \(=(v-1)\left[\sum_{v \in V} d^{+}(v)-\sum_{v \in V} d^{-}(v)\right]=0.\)
注意有向图性质：
\(d^{+}(v)+d^{-}(v)=v-1,\)
\(\sum_{v \in V} d^{+}(v)=\sum_{v \in V} d^{-}(v)=\varepsilon.\)
总结
| 无向图 | 有向图 | |
|---|---|---|
| 度边关系 | \(\sum\limits_{v\in V(G)}d(v)=2\epsilon\) | \(\sum\limits_{v\in V(\vec{G})}d^{+}(v)=\sum\limits_{v\in V(\vec{G})}d^{-}(v)=\epsilon\) |
| 含圈 | \(\delta(G)\ge2\) （充分条件） | \(\exists \vec{H}\subseteq\vec{G}:\forall v\in V(\vec{H}),d^{+}_H(v)>0\) （充要条件） |
| Euler闭迹 | 没有奇度顶点 | \(\forall v\in V(\vec{G}):d^{+}(v)=d^{-}(v)\) |
| Euler闭迹 | 可表成彼此无公共边的圈的并 | 可分解为彼此无公共边的有向圈的并 |
| Euler迹 | 至多含\(2\)个奇度顶点 | \(\exists
u,w\in
V(\vec{G}):d^{+}(u)=d^{-}(u)+1,d^{+}(w)=d^{-}(w)-1\)， 而其他顶点都有\(d^{+}(v)=d^{-}(v)\) |
| Hamilton圈 | （简单图）\(\forall u,v\in V(G):uv\notin E(G), d(u)+d(v)\ge\upsilon\) | （强连通简单）\(\forall u,v\in V(\vec{G}):\notin A(\vec{G}),d(u)+d(v)\ge 2\upsilon-1\) |
| Hamilton路 | / | （非平凡简单）\(\forall u,v\in V(\vec{G}):\notin A(\vec{G}),d(u)+d(v)\ge 2\upsilon-3\) |