オイラー路

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
全ての頂点の次数が偶数であるので、このグラフはオイラーグラフである。アルファベット順に辺をたどればオイラー閉路を得る。
ケーニヒスベルクの橋を簡略化したグラフ。このグラフはオイラーグラフではない。

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

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

オイラーの定理[編集]

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

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

脚注[編集]

  1. ^ Bollobas 1998, p. 16.

参考文献[編集]

関連項目[編集]