オイラー路
出典: フリー百科事典『ウィキペディア(Wikipedia)』
オイラー路とは、グラフの全ての辺を1度だけ通る路のこと。全ての辺を1度だけ通る閉路は、オイラー閉路という。オイラー閉路を含むグラフのことをオイラーグラフ、オイラー閉路は持たないがオイラー路を持つグラフのことを準オイラーグラフという。この名称は、レオンハルト・オイラーにちなむ。
オイラーグラフと準オイラーグラフは、一筆書き可能である。
- オイラーグラフ⇔全ての頂点の次数が偶数のグラフ
- 準オイラーグラフ⇔奇数の次数の頂点を二つだけ含むグラフ
カテゴリ: 数学関連のスタブ項目 | グラフ理論 | 数学に関する記事