FindEulerianCycle

FindEulerianCycle[g]
グラフ g のオイラー(Euler)回路を求める.

FindEulerianCycle[g,k]
最高で k 個のオイラー回路を求める.

詳細詳細

予備知識
予備知識

  • FindEulerianCycleは,グラフ内の他と区別できる1つ以上のオイラー(Euler)回路(オイラー閉路,オイラー路とも呼ばれる)を見付けようと試みる.閉路は,辺リストのリストとして,あるいは見付からない場合にはとして返される.オイラー回路(閉路が特定の端点を持つ明示的な経路を使って識別される場合には,より正しくは回路と呼ばれる)は,最初と最後の辺が端点で繋がり,各辺が厳密に1度だけ現れるような,互いに区別の付く辺の連続する列である.オイラー回路は,ゲノム配列を再構築したり,De Bruijin配列を構築したり,最適な学会のスケジューリングを求めたりするのに使える.
  • FindEulerianCycle[g,k]は,k 個のオイラー回路を求めようと試みる.オイラー回路では,回数指定 k を省略する(その場合には1であると見なされる)場合も,正の整数の場合も,あるいはAllになる場合もある.オイラー回路は,単純な閉路である必要はない.つまり,(必ず単純であるハミルトン(Hamilton)閉路とは違って)閉路内で頂点が繰り返されてもよい.
  • オイラー回路を含むグラフはオイラーグラフと呼ばれる.ただし, 「Euler」と「Eulerian」で使い分けて,つまり「Euler graph」ですべての頂点が偶次数であるグラフを指すとする場合もあるので注意が必要である.後者の定義は,連結した単純グラフは奇次数の頂点がない場合,かつその場合に限り,オイラー回路を持つというオイラーの正しい(彼自身によって証明されることはなかった)観察によるものである.オイラー回路はこのため,ハミルトン(Hamiltonian)閉路よりも数学的に研究しやすい. 個のノードを持つ連結したオイラー(Euler)グラフの数は, 個のノードを持つ連結したオイラー(Eulerian)グラフの数と等しいが,非連結のグラフについては数が異なる.どの閉路もすべての辺を通らないという場合でも,各ノードで複数の非連結の閉路を持つ非連結グラフが存在するからである.
  • EulerianGraphQは,グラフがオイラー(Eulerian)グラフであるかどうかを判断するのに使える.他の種類の閉路を見付けるための関数として,FindCycleFindHamiltonianCycleがある.
2010年に導入
(8.0)
| 2014年に修正
(10.0)