オーレの定理

オーレの定理は、 1960年にノルウェーの数学者オイステイン・オーレによって証明されたグラフ理論の結果である。これはグラフがハミルトングラフとなるための十分条件を与え、本質的には、十分な数の辺を持つグラフにはハミルトン閉路が含まれていなければならないことを述べている。具体的には、この定理は隣接していない頂点のペアの次数の合計を考慮している。つまり、そのようなすべてのペアの合計がグラフ内の頂点の総数と少なくとも等しい場合、そのグラフはハミルトングラフである。

G をn ≥ 3頂点を持つ（有限かつ単純な）グラフとする。Gにおける頂点vの次数、つまりGからvにつながる辺の数をdeg vで表す。すると、オーレの定理によれば、

Gはハミルトニアンです。

これは、すべての非ハミルトングラフG が条件(∗)に従わないことを示すことと同等です。したがって、G をハミルトンでないn ≥ 3頂点のグラフとし、ハミルトン閉路を作らない辺を 1 つずつ、辺を追加できなくなるまで追加してGからHを形成するとします。 xとy をH内の任意の 2 つの非隣接頂点とします。次に、辺xy をHに追加すると、少なくとも 1 つの新しいハミルトン閉路が作成され、そのような閉路内のxy以外の辺は、 x = v ₁およびy = v _nとして、H内でハミルトンパスv ₁ v ₂ ... v _{n を}形成する必要があります。 2 ≤ i ≤ n の範囲の各インデックスiについて、 H内でv ₁からv _iへ、およびv _{i − 1から}v _nへの 2 つの可能な辺を検討します。Hにはこれら 2 つの辺のうち最大で 1 つしか存在できません。そうでない場合、サイクルv ₁ v ₂ ... v _{i − 1} v _n v _{n − 1} ... v _{i は}ハミルトンサイクルになります。したがって、v ₁またはv _nに接続する辺の合計数は、最大でiの選択数、つまりn − 1に等しくなります。したがって、H は、この辺の合計数 ( deg v ₁ + deg v _n ) がn以上であることを要求する特性(∗)には従いません。 Gの頂点次数は最大でHの次数に等しいため、 Gも特性(∗)に従わない ことになります。

Palmer (1997) は、Ore の条件を満たすグラフでハミルトン閉路を構築するための次の簡単なアルゴリズムを説明しています。

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回しか発生しません。ここで、 nは指定されたグラフ内の頂点の数です。定理の証明と同様の議論により、目的のインデックスj が存在する必要があります。そうでない場合、隣接していない頂点v _iとv _{i  + 1 の}合計次数が小さすぎます。iとj を見つけて、サイクルの一部を逆にすることは、すべて O( n ) の時間で実行できます。したがって、アルゴリズムの合計時間は O( n ² ) であり、入力グラフのエッジの数と一致します。

オーレの定理は、各頂点の次数が少なくともn /2の場合、グラフはハミルトンであるというディラックの定理の一般化です。グラフがディラックの条件を満たす場合、明らかに各頂点のペアの次数は少なくともnになります。

次に、オーレの定理はボンディ・クヴァタール定理によって一般化されます。グラフ上で閉包操作を定義すると、隣接しない 2 つの頂点の次数が少なくともnを超える場合は常に、それらを接続する辺を追加します。グラフがオーレの定理の条件を満たす場合、その閉包は完全グラフです。ボンディ・クヴァタール定理は、グラフがハミルトンであるためには、その閉包がハミルトンである必要があると述べています。完全グラフはハミルトンであるため、オーレの定理が直ちに得られます。

Woodall (1972) は、有向グラフに適用される Ore の定理のバージョンを発見しました。有向グラフGが、任意の 2 つの頂点uおよびvに対して、 uからvへの辺が存在するか、uの出次数とvの入次数の合計がGの頂点数以上である、という特性を持つとします。この場合、Woodall の定理によれば、Gには有向ハミルトン閉路が含まれます。Woodall の定理では、任意の無向グラフのすべての辺を有向辺のペアで置き換えることで、Ore の定理を得ることができます。Meyniel (1973) による関連の深い定理では、隣接していない任意の 2 つの頂点uおよびvに対して、 uまたはvに接続する辺の総数が少なくとも 2 n − 1 である、という特性を持つn頂点の強連結有向グラフは 、ハミルトンでなければならないと述べています。

オーレの定理は、定理の次数条件の結果として、ハミルトン性よりも強い結論を与えるように強化されることもあります。具体的には、オーレの定理の条件を満たすすべてのグラフは、正則な 完全二部グラフであるか、または汎巡回グラフです(Bondy 1971)。

• ボンディ、JA（1971）、「パンサイクリックグラフI」、組み合わせ理論ジャーナル、シリーズB、11（1）：80–84、doi：10.1016 / 0095-8956（71）90016-5。
• Meyniel, M. (1973)、「サーキット ハミルトニエン ダン グラフ オリエンテにおける存在条件の不足」、Journal of Combinatorial Theory、シリーズ B (フランス語)、14 (2): 137–147、doi : 10.1016 /0095-8956(73)90057-9。
• オーレ、Ø. (1960)、「ハミルトン回路に関する注記」、アメリカ数学月刊誌、67 (1): 55、doi :10.2307/2308928、JSTOR  2308928。
• パーマー、EM（1997）、「ハミルトンサイクルに関するオーレの定理の隠れたアルゴリズム」、Computers & Mathematics with Applications、34（11）：113–119、doi：10.1016 / S0898-1221（97）00225-3、MR  1486890。
• Woodall, DR (1972)、「グラフの回路の十分条件」、ロンドン数学会紀要、第 3 シリーズ、24 : 739–755、doi :10.1112/plms/s3-24.4.739、MR  0318000。