完全有向グラフはハミルトンパスを持つ

$n$ 頂点の完全グラフ $(n\geq 2)$ の各辺に向きが与えられたものを $n$ 頂点の完全有向グラフといいます。例えば下の図のようなものです。

f:id:fibonacci_freak:20170713030148p:plain

実は完全有向グラフには必ずハミルトンパスが存在します。ハミルトンパスとは全ての頂点を1回ずつ通る道のことです（閉路でなくても構いません）。

頂点 $A$ から $B$ への有向辺が存在することを $A\to B$ と表すことにします。

定理. 任意の完全有向グラフ $G$ にはハミルトンパスが存在する。

証明. 頂点数 $n$ についての帰納法で示す。 $n=2$ のときは明らか。 $n\gt 2$ の場合、頂点を任意に1つとり $V$ とする。 $G-V$ ( $V$ を除いた部分グラフ)には帰納法の仮定によりハミルトンパス $A_1\to A_2\to\cdots\to A_{n-1}$ が存在する。 $V\to A_1$ または $A_{n-1}\to V$ ならばそれを道の端に追加することでハミルトンパスを得る。そうでない場合 $A_1\to V$ かつ $V\to A_{n-1}$ なので、 $A_i\to V$ かつ $V\to A_{i+1}$ なる $i\lt n$ が存在する（下図）。この時 $A_1\to\cdots\to A_i\to V\to A_{i+1}\to \cdots\to A_{n-1}$ なるハミルトンパスが取れる。 $\square$

f:id:fibonacci_freak:20170713030438p:plain

ところで、完全有向グラフの頂点があるハミルトンパスの始点になるための条件は簡単にわかるのでしょうか？これと似た条件として次のような概念を考えてみましょう。

定義. 完全有向グラフの頂点 $V$ が基点であるとは、 $V$ から任意の他の頂点への道が存在することを指す。先ほどの定理より、基点は必ず存在する。

例えば下の図で左下の頂点は基点です。

f:id:fibonacci_freak:20170713030337p:plain

基点であることは見かけ上「ハミルトンパスの始点」より弱い条件ですが、実は次が成り立ちます。

定理. 完全有向グラフ $G$ の頂点 $V$ があるハミルトンパスの始点になることと基点であることは同値である。

証明. ハミルトンパスの始点ならば基点であることは明らかなので逆を示す。頂点数 $n$ についての帰納法による。 $n=2$ の場合は明らか。 $n\gt 2$ の場合、 $V\to A$ なる頂点 $A$ 全体のなす部分グラフを $S$ とし、 $S$ の基点 $V'$ を取る。これは $G-V$ の基点でもある。実際 $W\in G-V$ に対し $V$ からの最短のハミルトンパス $V\to A\to\cdots\to W$ を取れば、 $V'$ から $A$ への( $S$ 内の)道と $A$ から $W$ への道を連結することで $V'$ から $W$ への道が得られる（下図）。よって帰納法の仮定より $V'$ を始点とする $G-V$ のハミルトンパスが存在するので、この先頭に $V\to V'$ を連結すればよい。 $\square$