4.8. ハミルトン路とハミルトン閉路
単純有向グラフに対するハミルトン路とハミルトン閉路は単純グラフの場合と同様に定義できる:
\(D=\left( V,A\right) \) を単純有向グラフとする。
-
\(D\) のハミルトン路 (Hamiltonian path) とは、\(D\) の各頂点をちょうど一度ずつ含む歩道を言う。明らかに、ハミルトン路は路である。
-
\(D\) のハミルトン閉路 (Hamiltonian cycle) とは、\(D\) の閉路 \(\left( v_{0},v_{1},\ldots,v_{k}\right) \) であって \(D\) の各頂点が \(v_{0},v_{1},\ldots,v_{k-1}\) にちょうど一度ずつ含まれるものを言う。
有向グラフにおけるハミルトン路とハミルトン閉路に関して何が言えるだろうか？ Ore の定理 (定理 2.14.4) に対応する事実は存在するだろうか？ この質問への答えは「存在する」である。しかし、その証明は格段に難しい:
\(n\) 個の頂点を持ちループを持たない強連結な単純有向グラフを \(D=\left( V,A\right) \) とする。三つの条件「\(u\neq v\)」と「\(\left( u,v\right) \notin A\)」と「\(\left( v,u\right) \notin A\)」を満たす任意の頂点の組 \(\left( u,v\right) \in V\times V\) が \(\deg u+\deg v\geq2n-1\) を満たすと仮定する (\(\deg w\) は \(\deg^{+}w+\deg^{-}w\) を意味する)。このとき \(D\) はハミルトン閉路を持つ。
この定理の (非常に複雑な) 証明は [BonTho77] または [Berge91, § 10.3] から確認できる。なお、\(D\) が強連結という条件は必須である。