オイラー経路

グラフ理論において、オイラー経路（またはオイラーパス）とは、有限グラフにおいてすべての辺を1度だけ訪れる経路（頂点の再訪問が可能）のことである。同様に、オイラー回路またはオイラーサイクルとは、同じ頂点で始まり、終わるオイラー経路のことである。これらは、1736年にレオンハルト・オイラーが有名なケーニヒスベルクの7つの橋問題を解く際に初めて議論された。この問題は、数学的には次のように表現できる。

画像のグラフが与えられた場合、各エッジを正確に 1 回訪れるパス(またはサイクル、つまり同じ頂点で始まり、終わるパス) を構築することは可能ですか?

オイラーは、オイラー閉路が存在するための必要条件はグラフ内のすべての頂点の次数が偶数であることだことを証明し、すべての頂点の次数が偶数である連結グラフにはオイラー閉路が存在することを証明なしに述べた。この後者の主張の最初の完全な証明は、1873年にカール・ヒアホルツァーによって死後に出版された。^[1]これはオイラーの定理として知られている。

連結グラフにオイラー閉路が存在するのは、すべての頂点の次数が偶数である場合のみです。

オイラーグラフという用語には、グラフ理論において2つの一般的な意味があります。1つはオイラー閉路を持つグラフ、もう1つはすべての頂点の次数が偶数であるグラフです。これらの定義は連結グラフでは一致します。^[2]

オイラートレイルが存在するためには、0 個または 2 個の頂点が奇数次であることが必要です。つまり、ケーニヒスベルク グラフはオイラーではありません。奇数次頂点がない場合、すべてのオイラートレイルは回路です。奇数次頂点がちょうど 2 個ある場合、すべてのオイラートレイルはそのうちの 1 個から始まり、もう 1 個で終わります。オイラートレイルはあるがオイラー回路はないグラフは、半オイラーと呼ばれます。

無向グラフにおけるオイラートレイル[^{注 1]} またはオイラーウォークは、各辺を1回だけ使用するウォークです。このようなウォークが存在する場合、そのグラフはトラバース可能または半オイラー的であると呼ばれます。^[3]

無向グラフにおけるオイラー閉路 [note 1] は、オイラー回路またはオイラー巡回とも呼ばれ、各辺を一度だけ使用する閉路である。この^ような閉路が存在する場合、グラフはオイラーまたは一筆書きグラフと呼ばれる。[ 4 ]「^オイラー グラフ」という用語は、すべての頂点の次数が偶数であるグラフを表すために、より弱い意味で使用されることもある。有限連結グラフの場合、2 つの定義は同等であるが、連結されていない可能性のあるグラフは、連結された各コンポーネントにオイラー閉路がある場合に限り、より弱い意味でオイラーである。

有向グラフの場合、「パス」を有向パスに、「サイクル」を有向サイクルに置き換える必要があります。

オイラー軌跡、サイクル、グラフの定義と特性は、マルチグラフにも有効です。

無向グラフGのオイラー配向は、各頂点vにおいてvの入次数がvの出次数と等しくなるように、Gの各辺に方向を割り当てることです。このような配向は、すべての頂点の次数が偶数である任意の無向グラフに存在し、Gの各連結成分でオイラー巡回を構築し、その巡回に従って辺を配向することで見つけることができます。^[5]連結グラフのすべてのオイラー配向は強い配向であり、結果として得られる有向グラフが強く連結される配向です。

• 無向グラフがオイラー閉路を持つためには、すべての頂点の次数が偶数で、次数が0でないすべての頂点が単一の連結成分に属している必要がある。^[6]
• 無向グラフは、すべての頂点の次数が偶数である場合にのみ、辺が互いに素なサイクルに分解できます。したがって、グラフがオイラーサイクルを持つのは、辺が互いに素なサイクルに分解でき、次数がゼロでない頂点が単一の接続コンポーネントに属している場合のみです。
• 無向グラフがオイラー軌跡を持つのは、ちょうど0または2個の頂点が奇数次数を持ち、その非ゼロ次数を持つすべての頂点が単一の連結成分に属する場合に限られます。^[6]
• 有向グラフがオイラー閉路を持つのは、すべての頂点の入次数と出次数が等しく、次数がゼロでないすべての頂点が単一の強連結成分に属する場合に限られます。同様に、有向グラフがオイラー閉路を持つのは、辺が互いに素な有向閉路に分解でき、次数がゼロでないすべての頂点が単一の強連結成分に属する場合に限られます。^[6]
• 有向グラフがオイラー軌跡を持つためには、最大で1つの頂点が(出次数) − (入次数) = 1を持ち、最大で1つの頂点が(入次数) − (出次数) = 1を持ち、他のすべての頂点が等しい入次数と出次数を持ち、その非ゼロ次数の頂点がすべて基礎となる無向グラフの単一の接続成分に属している必要がある。^[6]

フルーリーのアルゴリズムは、1883 年にまで遡る、簡潔だが非効率的なアルゴリズムです。 ^[7]すべての辺が同じコンポーネントにあり、奇数次数の頂点が最大 2 つあることがわかっているグラフを考えてみましょう。アルゴリズムは奇数次数の頂点から開始します。グラフに奇数次数がない場合には、任意に選択した頂点から開始します。各ステップで、パス内の次の辺として、削除してもグラフが切断されない辺を選択します。ただし、そのような辺がない場合は、現在の頂点に残っている辺を選択します。次に、その辺のもう一方の端点に移動して、辺を削除します。アルゴリズムの最後には、残っている辺はなく、辺が選択されたシーケンスは、グラフに奇数次数の頂点がない場合はオイラー閉路を形成し、奇数次数の頂点がちょうど 2 つある場合はオイラー トレイルを形成します。

Fleury のアルゴリズムにおけるグラフ走査はエッジの数に対して線形、すなわち ですが、ブリッジの検出の複雑さ も考慮する必要があります。すべてのエッジを削除した後にTarjanの線形時間ブリッジ検出アルゴリズム^[8]を再実行すると、Fleury のアルゴリズムの時間計算量は になります。Thorup (2000) の動的ブリッジ検出アルゴリズムを使用すると、これを まで改善できますが、それでも他のアルゴリズムよりも大幅に遅くなります。 ${\displaystyle O(|E|)}$${\displaystyle O(|E|^{2})}$${\displaystyle O(|E|\cdot \log ^{3}|E|\cdot \log \log |E|)}$

Hierholzerの 1873 年の論文では、Fleury のアルゴリズムよりも効率的なオイラー閉路を見つける別の方法が提供されています。

• 任意の開始頂点vを選択し、その頂点からvに戻るまでエッジの軌跡をたどります。すべての頂点の次数が偶数であるため、軌跡が別の頂点wに入るときに、 wから出る未使用のエッジが必ず存在するため、 v以外の頂点で行き詰まることはありません。このようにして形成されたツアーは閉じたツアーですが、最初のグラフのすべての頂点とエッジをカバーしない可能性があります。
• 現在のツアーに属しているが、ツアーの一部ではない隣接エッジを持つ頂点u が存在する限り、 uから別のトレイルを開始し、 uに戻るまで未使用のエッジをたどり、このようにして形成されたツアーを前のツアーに結合します。
• 元のグラフは接続されていると想定しているため、前の手順を繰り返すと、グラフのすべてのエッジが使い尽くされます。

各頂点に付随する未使用のエッジのセット、現在のツアー上の未使用のエッジを持つ頂点のリスト、およびツアー自体を維持するために、二重リンクリストなどのデータ構造を使用することで、アルゴリズムの個々の操作（各頂点から出る未使用のエッジの検索、ツアーの新しい開始頂点の検索、および頂点を共有する2つのツアーの接続）はそれぞれ定数時間で実行できるため、アルゴリズム全体では線形時間、かかります。^[9]${\displaystyle O(|E|)}$

このアルゴリズムはdequeを使って実装することもできます。deque が閉じたツアーを表す場合にのみスタックが発生する可能性があるため、deque を回転させて、スタックが解除されるまで末尾からエッジを削除し、それらを先頭に追加し、すべてのエッジが考慮されるまで続けます。実行される回転の数は(直感的に、すべての「不良」エッジは先頭に移動され、新しいエッジは末尾に追加されます) を 超えることはないため、これも線形時間がかかります。${\displaystyle |E|}$

有向グラフ内のオイラー閉路の数は、de Bruijn、van Aardenne- Ehrenfest、S mith、Tutteにちなんで名付けられたいわゆるBEST 定理を使用して計算できます。この式は、有向グラフ内のオイラー閉路の数は、特定の次数の階乗と根付き樹枝の数の積であるとしています。後者は、行列木定理によって行列式として計算でき、多項式時間アルゴリズムが得られます。

BEST 定理は、アーデンヌ＝エーレンフェストとデ・ブリュインの論文 (1951) の「証明に追加された注記」でこの形で初めて述べられました。元の証明は単射であり、デ・ブリュイン列を一般化しました。これは、スミスとタット (1941) による以前の結果のバリエーションです。

無向グラフ上のオイラー回路の数を数えることははるかに困難です。この問題は#P 完全であることが知られています。^[10]肯定的な方向では、マルコフ連鎖モンテカルロアプローチは、コッツィグ変換（ 1968年にアントン・コッツィグによって導入）を介して、グラフ内のオイラー回路の数の明確な近似値を与えると信じられていますが、この事実はまだ証明されていません（制限された次数のグラフであっても）。

完全グラフにおけるオイラー閉路の数の漸近式は、マッケイとロビンソン（1995）によって決定された： ^[11]

${\displaystyle \operatorname {ec} (K_{n})=2^{\frac {(n+1)}{2}}\pi ^{\frac {1}{2}}e^{{\frac {-n^{2}}{2}}+{\frac {11}{12}}}n^{\frac {(n-2)(n+1)}{2}}{\bigl (}1+O(n^{-{\frac {1}{2}}+\epsilon }){\bigr )}.}$

同様の式は後にMI Isaev (2009)によって完全な二部グラフに対して得られた: ^[12]

${\displaystyle \operatorname {ec} (K_{n,n})=\left({\frac {n}{2}}-1\right)!^{2n}2^{n^{2}-n+{\frac {1}{2}}}\pi ^{-n+{\frac {1}{2}}}n^{n-1}{\bigl (}1+O(n^{-{\frac {1}{2}}+\epsilon }){\bigr )}.}$

オイラートレイルはバイオインフォマティクスにおいて、 DNA配列を断片から再構築するために使用されます。 ^{[13]また、} CMOS回路設計において、最適な論理ゲートの順序を見つけるためにも使用されます。^[14]ツリーを処理するためのアルゴリズムの中には、ツリーのオイラーツアー（各エッジが一対の弧として扱われる）に依存するものがあります。^{[15] [16]} de Bruijnシーケンスは、de Bruijnグラフのオイラートレイルとして構築できます。^[17]

無限グラフにおいて、オイラートレイルまたはオイラーサイクルに対応する概念は、グラフのすべての辺をカバーする二重無限トレイルであるオイラー直線である。このようなトレイルが存在するためには、グラフが連結され、すべての頂点の次数が偶数であることだけでは不十分である。たとえば、すべての頂点の次数が 4 である無限ケイリーグラフにはオイラー直線がない。オイラー直線を含む無限グラフは、エルデシュ、グリュンワルド、ワイスフェルド (1936) によって特徴付けられた。無限グラフまたは多重グラフG がオイラー直線を持つためには、次の条件がすべて満たされることが必要かつ十分である: ^{[18] [19]}

• Gは接続されています。
• G には頂点と辺の可算な集合があります。
• G には（有限の）奇数次数の頂点はありません。
• Gから任意の有限サブグラフS を削除すると、残りのグラフには最大 2 つの無限連結コンポーネントが残ります。また、Sの各頂点の次数が偶数の場合、S を削除すると、正確に 1 つの無限連結コンポーネントが残ります。

オイラーは、有限グラフがオイラーグラフであるための必要条件として、すべての頂点の次数が偶数でなければならないと述べた。ヒアホルツァーは、1873年に発表された論文でこれが十分条件であることを証明した。これにより、有限グラフがオイラーグラフであるために必要な次の必要かつ十分なステートメントが導かれる。無向連結有限グラフがオイラーグラフであるためには、Gのすべての頂点の次数が偶数でなければならない。^[20]

以下の結果は1912年にヴェブレンによって証明された。無向連結グラフがオイラーグラフであるのは、それがいくつかの閉路の互いに素な和集合である場合のみである。^[20]

Hierholzer は、無向グラフでオイラー巡回を構築するための線形時間アルゴリズムを開発しました。

出次数が全て偶数であるがオイラーではない有向グラフが存在する可能性もある。オイラー閉路は頂点に入る回数と同じ回数だけ頂点から出るので、オイラー閉路が存在するための必要条件は、各頂点の入次数と出次数が等しいことである。明らかに、連結性も必要である。ケーニヒはこれらの条件も十分であることを証明した。つまり、有向グラフがオイラーであるためには、連結されており、各頂点の入次数と出次数が等しい必要がある。^[20]

この定理では、「連結」が「弱連結」を意味するか「強連結」を意味するかは問題ではありません。なぜなら、それらはオイラーグラフの場合同等だからです。

オイラー巡回を構築するためのヒアホルツァーの線形時間アルゴリズムは有向グラフにも適用できる。^[20]

偶数かつ対称な混合グラフはすべてオイラーグラフであることが保証されている。しかし、これは必要条件ではなく、非対称で偶数でもオイラーグラフを構成することが可能である。^[20]

フォードとフルカーソンは1962年に著書「Flows in Networks」で、グラフがオイラーグラフであるための必要十分条件を証明した。すなわち、すべての頂点が偶数でバランス条件を満たす必要がある、つまり頂点Sのすべての部分集合について、Sから出る弧の数とSに入る弧の数の差がSに接続する辺の数以下でなければならない、という条件である。^[20]

混合グラフがオイラーグラフであるかどうかを確認するプロセスは、無向グラフまたは有向グラフがオイラーグラフであるかどうかを確認するプロセスよりも困難です。これは、均衡集合条件が頂点のすべての可能なサブセットに関係するためです。

• オイラーマトロイド、オイラーグラフの抽象的一般化
• 5つの部屋パズル
• 握手補題はオイラーが原著論文で証明したもので、任意の無向連結グラフには奇数次頂点が偶数個あることを示している。
• ハミルトン経路– 各頂点を正確に 1 回訪れる経路。
• ルート検査問題。オイラー経路が存在しない場合はエッジを繰り返しながら、すべてのエッジを訪れる最短経路を検索します。
• ヴェブレンの定理は、頂点次数が偶数のグラフは、その接続性に関係なく、辺が互いに素なサイクルに分割できるというものである。

• エルドシュ, パル; Grünwald, ティボール州; Weiszfeld, Endre (1936)、「Végtelen gráfok Euler vonalairól」[無限グラフのオイラー線について] (PDF)、Mat.修理。ラポク(ハンガリー語)、43 : 129–140。エルデシュ、P.として翻訳。グリュンヴァルト、T . ; Vázsonyi、E. (1938)、「Über Euler-Linien unendlicher Graphen」[無限グラフのオイラー直線について] (PDF)、J. Math.物理学。 (ドイツ語)、17 (1–4): 59–75、doi :10.1002/sapm193817159。
• オイラー、L.、「幾何学的な問題の解決策」、コメント。科学アカデミーI. Petropolitanae 8 (1736)、128–140。
• Hierholzer、Carl (1873)、「Ueber die Möglichkeit、einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren」、Mathematische Annalen、6 (1): 30–32、doi :10.1007/BF01442866、S2CID  119885172。
• Lucas, E.、Récréations Mathématiques IV、パリ、1​​921 年。
• Fleury、「状況の幾何学問題」、Journal de mathematiques elementaires (1883)、257–261。
• T. van Aardenne-EhrenfestおよびNG de Bruijn (1951)「有向線形グラフの回路とツリー」、Simon Stevin 28: 203–217。
• Thorup, Mikkel (2000)、「ほぼ最適な完全動的グラフ接続」、Proc. 32nd ACM Symposium on Theory of Computing、pp. 343–350、doi :10.1145/335305.335345、S2CID  128282
• WT TutteとCAB Smith (1941)「次数 4 のネットワークにおける一筆書きパスについて」、American Mathematical Monthly 48: 233–237。

ウィキメディア・コモンズには、オイラー経路に関連するメディアがあります。

• Fleury のアルゴリズムに関する初期の言及についての議論。
• 数学百科事典のオイラーツアー。