オイラー路

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

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

 オイラーの定理 

オイラーグラフと準オイラーグラフは、一筆書き可能である。連結グラフ G に対して次が成り立つ。
G がオイラーグラフ ⇔ G の全ての頂点の次数が偶数。
G が準オイラーグラフ ⇔ G の頂点のうち、次数が奇数であるものが2つ。

 脚注 

 参考文献 

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

Category:グラフ理論
Category:数学に関する記事
Category:レオンハルト・オイラー