オイラー路

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

オイラー路とは、グラフ(グラフ理論)の全ての辺を1度だけ通るのこと。全ての辺を1度だけ通る閉路は、オイラー閉路という。この名称は、レオンハルト・オイラーにちなむ。

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

オイラーグラフと準オイラーグラフは、一筆書き可能である。連結グラフ G に対して次が成り立つ。(詳細は一筆書きの記事参照)

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

グラフG頂点をすべて通る閉路はハミルトン路という。

関連項目[編集]