オイラー路

オイラー路（オイラーろ、英: Eulerian trail）とは、グラフの全ての辺を通る路のこと。また全ての辺をちょうど1度だけ通る閉路は、オイラー閉路（オイラーへいろ、英: Euler circuit）という。これらの名称は1736年にこれらを含むグラフの特徴づけを与えたレオンハルト・オイラーにちなむ。

全ての頂点の次数が偶数であるので、このグラフはオイラーグラフである。アルファベット順に辺をたどればオイラー閉路を得る。

ケーニヒスベルクの橋を簡略化したグラフ。このグラフはオイラーグラフではない。

グラフの辺をすべて通るようなオイラー閉路を持つグラフのことをオイラーグラフ（英: Eulerian graph）という。またグラフの辺をすべて通るような、閉路でないオイラー路を持つグラフのことを準オイラーグラフという。

オイラーの定理

→「一筆書き」も参照

オイラーグラフと準オイラーグラフは、一筆書き可能である。連結グラフ G に対して次が成り立つ。

• G がオイラーグラフ ⇔ G の全ての頂点の次数が偶数。
• G が準オイラーグラフ ⇔ G の頂点のうち、次数が奇数であるものが2つ。

参考文献

• Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics. 184. Springer. ISBN 0-387-98491-7. https://books.google.co.jp/books?id=SbZKSZ-1qrwC&pg=PA16 

関連項目

• ケーニヒスベルクの問題
• ハミルトン路：すべての頂点を通る路