オイラー路


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

オイラー路

すべての辺を一度だけ通る路をオイラー路という。一筆書きできるとも言い換えられる。

オイラー路が閉路の場合、特にオイラー閉路であるという。

(その他の語彙)

  • あるノードの次数とはそのノードに繋がる辺の数を表す。
  • 入次数(いりじすう)はそのノードに入り込む辺であり、出次数(でじすう)は反対にそのノードから出て行く辺である。
  • 相対次数は入次数と出次数の差の絶対値を表す。

無向オイラー路

無向オイラー路を形成する、連結グラフGにおいて

  • Gが閉路となる:各ノードの次数が偶数である
  • Gが閉路でない:次数が奇数のノードが2つ限り存在する

有向オイラー路

有向オイラー路を形成する、連結グラフGにおいて

  • Gが閉路となる:各ノードの相対次数が0(入次数と出次数が等しい)
  • Gが閉路でない:入次数-出次数 = 1、出次数-入次数 = 1 となるノードが1つずつ存在し、他のノードは相対次数が0

グラフが連結であること

オイラー路の問題を解く際は、注目するグラフが必ず連結である必要がある。(繋がっていないノードが存在しない)

連結であることが確かで無い場合、DFSをかけて全てのノードを辿れるか否かで連結判定をすれば良い。

無向オイラー路は閉路の如何に関わらず適当なノード一つからDFSをすれば連結判定が可能。

有向オイラー路において、閉路でない場合のみ入次数が1のノードから連結判定を始められるように工夫をする必要がある。すべてのノードを始点としてDFSをするか、またはグラフを無向グラフに書き換えてDFSをかけるかなどの方法が考えられる。