オイラー路
表示
この記事は英語版の対応するページを翻訳することにより充実させることができます。(2024年4月) 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
オイラー路(オイラーろ、英: Eulerian trail)とは、グラフの全ての辺を通る路のこと。また全ての辺をちょうど1度だけ通る閉路は、オイラー閉路(オイラーへいろ、英: Euler circuit)という。これらの名称は1736年にこれらを含むグラフの特徴づけを与えたレオンハルト・オイラーにちなむ[1]。
グラフの辺をすべて通るようなオイラー閉路を持つグラフのことをオイラーグラフ(英: Eulerian graph)という。またグラフの辺をすべて通るような、閉路でないオイラー路を持つグラフのことを準オイラーグラフという。
オイラーの定理
[編集]「一筆書き」も参照
オイラーグラフと準オイラーグラフは、一筆書き可能である。連結グラフ G に対して次が成り立つ。
- G がオイラーグラフ ⇔ G の全ての頂点の次数が偶数。
- G が準オイラーグラフ ⇔ G の頂点のうち、次数が奇数であるものが2つ。
脚注
[編集]- ^ Bollobas 1998, p. 16.
参考文献
[編集]- Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics. 184. Springer. ISBN 0-387-98491-7
関連項目
[編集]- ケーニヒスベルクの問題
- ハミルトン路:すべての頂点を通る路