オーレの定理

ウィキペディア

オーレの定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/30 07:10 UTC 版)

オーレの定理の条件を満たし、ハミルトン閉路を持つグラフ。図の中央には次数が n/2 未満の頂点が2個存在するため、このグラフはディラックの定理の条件は満たさない。しかしこの2頂点は隣接しており、またこのペア以外のどの2頂点についても、次数の和はグラフの頂点数である7以上である。

オーレの定理（オーレのていり、英: Ore's theorem）は、ノルウェーの数学者 Øystein Ore によって1960年に証明されたグラフ理論の定理である。オアの定理とも表記される。これはグラフがハミルトングラフであるための十分条件を与えるもので、実質的に、グラフに十分多くの辺が存在していればハミルトン閉路を含んでいなければならないと述べている。特に、この定理ではグラフの隣接しない2頂点の次数の和について考える。もしこのような和が常にグラフの頂点数以上であれば、グラフはハミルトングラフである。

正式なステートメント

G が有限単純グラフで、頂点数 n ≥ 3 とする。G の頂点 v の次数（その頂点に接続する辺の数）を deg v と書く。このとき、

隣接しない任意の2頂点 v, w について deg v + deg w ≥ n

(∗)

であるなら、G はハミルトングラフである。

証明

オーレの定理の証明の図解。（閉じていない）ハミルトン路 v₁...v_n は存在するがハミルトン閉路は存在しないようなグラフについて、2本の辺 v₁v_i と v_{i − 1}v_n（青い破線で示した）のうち存在し得るのは高々1本である。なぜなら、もし両方とも存在するとすれば、ハミルトン路にそれらの2辺を加え、赤い辺 v_{i − 1}v_i を除去することによってハミルトン閉路ができてしまうからである。

任意の非ハミルトングラフ G が条件 (∗) を満たさないことを言えばよい。

そこで、G を頂点数 n ≥ 3 の非ハミルトングラフとし、これに辺を1本ずつ足していって、それ以上どのように辺を追加してもハミルトン閉路ができてしまうようなグラフを H とする。

x と y を H における任意の隣接しない2頂点とする。このとき xy をグラフ H に追加すると、1個以上のハミルトン閉路が生じる。この閉路から辺 xy を除いたものは H のハミルトンパス v₁v₂...v_n （ここで x = v₁, y = v_n ）である。

任意の添字 i (2 ≤ i ≤ n)に対し、v₁ から v_i への辺と v_{i − 1} から v_n への辺の存在について考えると、これらのうち存在するのは高々1本である。なぜなら、さもないと H で v₁v₂...v_{i − 1}v_nv_{n − 1}...v_i がハミルトン閉路になってしまうからである。

よって、頂点 v₁ または v_n に接続する辺の総数は最大でも添字 i の選び方の数、n − 1 である。よって deg v₁ + deg v_n が n 以上でないため、 H は条件 (∗) を満たさない。

グラフ G の頂点の次数は H での次数以下だから、G もやはり条件 (∗) を満たさない。

アルゴリズム

Palmer (1997) は、オーレの条件の条件を満たすグラフにおいてハミルトン閉路を構成する以下のようなシンプルなアルゴリズムを記述した。

1. 隣接性を無視し、グラフの頂点を閉路となるよう並べる。
2. この閉路で連続する2頂点 v_i, v_i + 1 が元のグラフで隣接していなかったら、以下の2つのステップを実行する。：
   • 4個の頂点 v_i, v_i + 1, v_j, v_j + 1 が相異なり、かつ、元のグラフで v_i と v_j、v_j + 1 と v_i + 1 がそれぞれ隣接しているような添字 j を探す。
   • 閉路内の v_i + 1 から v_j までの全ての頂点（両端も含む）を逆向きに並べる。

各ステップで、元のグラフで隣接しているような閉路内の連続する頂点対の数は、1または2だけ増加する（v_j と v_j + 1 が既に隣接している頂点対かどうかに依る）。そのため、アルゴリズムが停止するまでの閉路の拡張の回数は高々グラフの頂点数 n である。定理の証明で行ったものと同様の議論で、このような所望の添字 j は必ず存在する（さもなければ、隣接しない2頂点 v_i, v_i + 1 の次数の和は仮定の不等式を満たさない）。i と j の発見、閉路の一部の逆順並べ替えはいずれも計算時間 O(n) で行えるから、アルゴリズム全体の計算時間は O(n²) であり、これは入力するグラフの辺の数と同じオーダーである。

関連する結果

オーレの定理は（ハミルトン路に関する）ディラックの定理：

どの頂点の次数も n/2 以上であるようなグラフは、ハミルトングラフである。

を一般化したものである。ディラックの定理の条件が満たされていれば、明らかにどの2頂点の次数の和も n 以上になる。

一方、オーレの定理は Bondy–Chvátalの定理へと一般化される。グラフの閉包（closure）を、次数の和がグラフの頂点数 n 以上である任意の隣接しない2頂点間に1本の辺を追加する操作、と定義する。このとき Bondy–Chvátalの定理は

グラフがハミルトングラフであるための必要十分条件は、その閉包がハミルトングラフであることである。

という主張である。グラフがオーレの定理の条件を満たしていれば、その閉包は完全グラフであり、完全グラフはハミルトングラフであるから、オーレの定理は Bondy–Chvátalの定理よりただちに従う。

Woodall (1972) は、オーレの定理の有向グラフに適用できるバージョンを発見した。有向グラフ G が次の条件を満たすとする： 任意の2頂点 u と v に対し、u から v へ向かう辺が存在するか、もしくは u の出次数と v の入次数の和が G の頂点数以上である。

このとき G には有向ハミルトンサイクルが存在する（Woodallの定理）。オーレの定理は、与えられた無向グラフの全ての辺を両方向の2本の有向辺で置き換えれば、Woodallの定理から得ることができる。Meyniel (1973) による、これと深く関連した定理は以下の通りである：

n-頂点の強連結有向グラフで、任意の隣接しない2頂点 u, v に対し、u と v の少なくとも一方に接続する辺の本数が 2n − 1 以上であるものは、ハミルトングラフである。

次数に関する条件から、オーレの定理の結論は、ハミルトン性よりも強くすることができる。特に、オーレの定理の条件を満たすグラフは正則な完全2部グラフか、パンサイクリックグラフかのいずれかである (Bondy 1971)。

参考文献

• Bondy, J. A. (1971), “Pancyclic graphs I”, Journal of Combinatorial Theory, Series B 11 (1): 80–84, doi:10.1016/0095-8956(71)90016-5 .
• Meyniel, M. (1973), “Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté” (French), Journal of Combinatorial Theory, Series B 14 (2): 137–147, doi:10.1016/0095-8956(73)90057-9 .
• Ore, Ø. (1960), “Note on Hamilton circuits”, American Mathematical Monthly 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928, https://jstor.org/stable/2308928 .
• Palmer, E. M. (1997), “The hidden algorithm of Ore's theorem on Hamiltonian cycles”, Computers & Mathematics with Applications 34 (11): 113–119, doi:10.1016/S0898-1221(97)00225-3, MR1486890 .
• Woodall, D. R. (1972), “Sufficient conditions for circuits in graphs”, Proceedings of the London Mathematical Society, Third Series 24: 739–755, doi:10.1112/plms/s3-24.4.739, MR0318000 .