オイラー路とは、グラフのすべての辺をちょうど1回ずつ通る道のことです。このような道が始点と終点で同じ頂点に戻る場合は、オイラー閉路またはオイラーサイクルと呼びます。この概念はグラフ理論の中心的な考え方の一つで、与えられたグラフがそのような走査を許すかどうかを、簡単に判定できる条件を与えます。
基本的な特徴づけ
無向グラフでは、古典的な判定条件は単純です。連結なグラフがオイラー閉路をもつのは、すべての頂点の次数が偶数のときに限られます。オイラー路はあるが閉路ではないのは、グラフが連結で、ちょうど2つの頂点だけが奇数次数である場合に限られます。このとき、その路は一方の奇数次数頂点から始まり、もう一方で終わります。
有向グラフでは、条件は入次数と出次数で表されます。各頂点で入次数と出次数が等しく、かつ辺が1つの強連結成分に含まれている（孤立頂点を除く）とき、有向グラフはオイラー閉路をもちます。有向オイラー路は、多くの頂点で入次数と出次数が等しく、1つの頂点だけが出次数が入次数より1大きい（始点）、別の1つの頂点だけが入次数が出次数より1大きい（終点）ことに加え、適切な連結条件があるときに存在します。
歴史的背景
この考え方は、レオンハルト・オイラーが1736年に行ったケーニヒスベルクの七つの橋の解析に始まります。オイラーは、市内の各橋をちょうど1回ずつ渡る経路は存在しないことを証明し、その配置を頂点と辺からなる抽象的なネットワークへと還元しました。これは、グラフ理論とネットワークに関する考え方の基礎を築くものとなりました。
アルゴリズム
構成的な方法によって、オイラー路が存在する場合にはそれを実際に作ることができます。ヒエルホルツァーのアルゴリズムは、未使用の辺をたどり続け、できた閉路をつなぎ合わせることで、線形時間でオイラー閉路を求めます。フルーリーのアルゴリズムは概念的にはよりわかりやすいものの、橋となる辺を何度も調べるため、実用上はあまり効率的ではありません。これらの手順は、入門的なグラフアルゴリズムとして広く教えられています。
応用と例
オイラー路は、実用上のさまざまな問題に現れます。たとえば、経路検査や都市計画では、中国人郵便配達問題が、すべての辺をたどる最短の閉じた経路（同じ辺を重複して通ってもよい）を求めます。また、de Bruijnグラフでリードをモデル化するDNA組み立て法、公益施設ネットワークの点検、娯楽的なパズルなどにも現れます。単純な例としては、どのサイクルグラフも（すべての頂点が偶数次数なので）オイラー的であり、一本の経路グラフはちょうど2つの端点が奇数次数をもつため、オイラー閉路ではなくオイラー路をもちます。
区別と注目すべき点
- オイラー的かハミルトン的か：オイラーは辺を1回ずつ通ることを調べ、ハミルトンは頂点を1回ずつ訪れることを求めます。存在条件もアルゴリズムも異なります。
- オイラー路の判定は効率的です。次数の数え上げと連結性の検査で十分です。
- オイラーの考え方は、実際の経路問題を抽象的な組合せ条件へと変え、現代のネットワーク理論に影響を与えました。