「オイラー路」の編集履歴（バックアップ）一覧はこちら
「オイラー路」(2013/10/22 (火) 22:56:53) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*オイラー路
すべての辺を一度だけ通る路をオイラー路という。一筆書きできるとも言い換えられる。
オイラー路が閉路の場合、特にオイラー閉路であるという。
（その他の語彙）
-あるノードの次数とはそのノードに繋がる辺の数を表す。
-入次数（いりじすう）はそのノードに入り込む辺であり、出次数（でじすう）は反対にそのノードから出て行く辺である。
-相対次数は入次数と出次数の差の絶対値を表す。
**無向オイラー路
無向オイラー路を形成する、連結グラフGにおいて
-Gが閉路となる：各ノードの次数が偶数である
-Gが閉路でない：次数が奇数のノードが2つ限り存在する
**有向オイラー路
有向オイラー路を形成する、連結グラフGにおいて
-Gが閉路となる：各ノードの相対次数が0（入次数と出次数が等しい）
-Gが閉路でない：入次数-出次数 = 1、出次数-入次数 = 1 となるノードが1つずつ存在し、他のノードは相対次数が0
**グラフが連結であること
オイラー路の問題を解く際は、注目するグラフが必ず連結である必要がある。（繋がっていないノードが存在しない）
連結であることが確かで無い場合、DFSをかけて全てのノードを辿れるか否かで連結判定をすれば良い。
無向オイラー路は閉路の如何に関わらず適当なノード一つからDFSをすれば連結判定が可能。
有向オイラー路において、閉路でない場合のみ入次数が1のノードから始められるような工夫をする必要がある。入次数1のノードを記憶するか、すべてのノードを始点としてDFSをするか、またはグラフを無向グラフに書き換えてDFSをかけるかなどの方法が考えられる。
*オイラー路
すべての辺を一度だけ通る路をオイラー路という。一筆書きできるとも言い換えられる。
オイラー路が閉路の場合、特にオイラー閉路であるという。
（その他の語彙）
-あるノードの次数とはそのノードに繋がる辺の数を表す。
-入次数（いりじすう）はそのノードに入り込む辺であり、出次数（でじすう）は反対にそのノードから出て行く辺である。
-相対次数は入次数と出次数の差の絶対値を表す。
**無向オイラー路
無向オイラー路を形成する、連結グラフGにおいて
-Gが閉路となる：各ノードの次数が偶数である
-Gが閉路でない：次数が奇数のノードが2つ限り存在する
**有向オイラー路
有向オイラー路を形成する、連結グラフGにおいて
-Gが閉路となる：各ノードの相対次数が0（入次数と出次数が等しい）
-Gが閉路でない：入次数-出次数 = 1、出次数-入次数 = 1 となるノードが1つずつ存在し、他のノードは相対次数が0
**グラフが連結であること
オイラー路の問題を解く際は、注目するグラフが必ず連結である必要がある。（繋がっていないノードが存在しない）
連結であることが確かで無い場合、DFSをかけて全てのノードを辿れるか否かで連結判定をすれば良い。
無向オイラー路は閉路の如何に関わらず適当なノード一つからDFSをすれば連結判定が可能。
有向オイラー路において、閉路でない場合のみ入次数が1のノードから連結判定を始められるように工夫をする必要がある。すべてのノードを始点としてDFSをするか、またはグラフを無向グラフに書き換えてDFSをかけるかなどの方法が考えられる。
