MATHEMATICA 組込みシンボル

FindEulerianCycle

FindEulerianCycle[g]
グラフ g にオイラー(Euler)回路が存在する場合にそれを求める．

FindEulerianCycle

最高で k 個のオイラー回路を求める．

詳細

オイラー回路はすべての辺を厳密に1回通る回路である．

FindEulerianCycleはオイラー回路からなる経路のリストを返す．

FindEulerianCycleはオイラー回路が存在しない場合にはリストを返す．

FindEulerianCycle[g]は FindEulerianCycleに等しい．

例題

すべて閉じる

例 (2)

無向グラフの中にオイラー回路を求める：

有向グラフで：

無向グラフの中にオイラー回路を求める：

In[1]:=

Out[1]=

In[2]:=

Out[2]=

有向グラフで：

In[1]:=

Out[1]=

In[2]:=

Out[2]=

スコープ (5)

FindEulerianCycleは無向グラフに使うことができる：

有向グラフ：

最高で3つのオイラー回路を求める：

FindEulerianCycleは非オイラーグラフに対しては空の結果を返す：

大きいグラフに使う：

アプリケーション (3)

一筆書きで封筒の形をなぞる：

このグラフはオイラーグラフではない：

奇点が2つあるので，（多重辺を避けるために）新たな頂点を通して奇点を繋いで拡張したオイラーグラフを作ることができる：

拡張したグラフの中でオイラー回路を求める：

頂点

を含む辺が最後になるまで回路の辺を回転させる：

オイラー路を示す：

有向回路に沿って頂点が訪れられる順番を求める：

各辺のソース頂点を拾い出す：

無向回路に沿って頂点が訪れられる順番を求める：

経路は最初の辺の頂点から始まる．この頂点は最初の辺が自己ループでない限り2番目の辺の頂点ではない：

辺を順番に辿って頂点を求める：

特性と関係 (5)

EulerianGraphQを使ってグラフにオイラー回路があるかどうか調べる：

すべてのグラフ頂点が偶次数のときかつそのときに限り連結無向グラフにはオイラー回路がある：

無向グラフが辺非連結回路に分割できるとき，その無向グラフにはオイラー回路がある：

グラフが連結していて頂点と辺の数が等しいとき，そのグラフは回路である：

連結有向グラフについて：

無向オイラーグラフの線グラフにはオイラー回路がある：

すべての頂点の入次数と出次数が等しいときかつそのときに限り有向グラフにはオイラー回路がある：