読み方：オイラーろ

オイラー路【Eulerian path】

オイラー路とは？

グラフ理論における経路の一種で、グラフ上のすべての辺をちょうど一度ずつ通る経路のこと。辺を「一筆書き」する経路で、頂点（ノード）は何度通過してもよいが、辺（エッジ）を二度通ることはできない。出発点と終点が同じ閉じた経路は「オイラー閉路」（オイラー回路）と呼ばれ、出発点と終点が異なるものを狭義の「オイラー路」と呼ぶ。

18世紀のスイスの数学者レオンハルト・オイラー（Leonhard Euler）に由来する概念である。オイラーは1736年、ケーニヒスベルク市内を流れるプレーゲル川にかかる七本の橋を、それぞれ一度だけ渡ってすべて回れるか、という「ケーニヒスベルクの橋の問題」を解いた。オイラーはグラフを用いてこれを定式化し、「不可能である」と証明した。これがグラフ理論の始まりとされている。

オイラー路が存在するかどうかは、グラフの構造によって決まる。連結グラフにおいて、奇数本の辺が接続している頂点（奇数次数の頂点）がちょうど二つある場合、その二点を始点・終点とするオイラー路が存在する。奇数次数の頂点がまったく存在しない場合はオイラー閉路が存在し、奇数次数の頂点が三つ以上ある場合はオイラー路もオイラー閉路も存在しない。ケーニヒスベルクの橋の問題では奇数次数の頂点が四つあったため、条件を満たさなかった。

一筆書きが可能かどうかの判定は、まさにオイラー路の存在判定と同義であり、この考え方は日常の問題にも現れる。例えば、道路の清掃車や郵便配達のルート設計など、すべての道を無駄なく通過する経路を求める問題に応用される。コンピュータ科学の分野ではDNAの塩基配列解析（シーケンシング）でも活用されており、断片化された配列を再構成する際にオイラー路の探索が用いられる。

オイラー路を実際に求めるアルゴリズムとしては、フルーリー（Fleury）のアルゴリズムやヒールホルツァー（Hierholzer）のアルゴリズムが知られている。後者は時間効率がよく、辺の数をE、頂点の数をVとしたとき計算量がO（E+V）で済むため、大規模なグラフにも適用できる。オイラーが18世紀に提示したこの単純な問いは、グラフ理論という現代数学の一分野を生み出す契機となり、現在では組み合わせ最適化やネットワーク解析の基礎として広く参照されている。