WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

FindEulerianCycle[g]

グラフ g のオイラー(Euler)閉路を求める．

FindEulerianCycle[g,k]

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

FindEulerianCycle[{vw,…},…]

規則 vw を使ってグラフ g を指定する．

詳細
Details and Options Details and Options
予備知識
例題  
例  
スコープ  
アプリケーション  
特性と関係  
おもしろい例題  
関連項目
関連するガイド
履歴
引用書式

FindEulerianCycle

FindEulerianCycle[g]

グラフ g のオイラー(Euler)閉路を求める．

FindEulerianCycle[g,k]

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

FindEulerianCycle[{vw,…},…]

規則 vw を使ってグラフ g を指定する．

詳細

予備知識

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

例題

すべて開く すべて閉じる

例  (2)

オイラー閉路を求める：

Wolfram Language code: g = GraphData["OctahedralGraph"];
Wolfram Language code: FindEulerianCycle[g]

オイラー閉路を示す：

Wolfram Language code: Table[HighlightGraph[g, Part[First[%], 1 ;; i]], {i, Length[First[%]]}]

複数のオイラー閉路を求める：

Wolfram Language code: FindEulerianCycle[GraphData["ButterflyGraph"], 2]

スコープ  (8)

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

Wolfram Language code: FindEulerianCycle[[image]]

有向グラフ：

Wolfram Language code: FindEulerianCycle[[image]]

多重グラフ：

Wolfram Language code: FindEulerianCycle[[image]]

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

Wolfram Language code: FindEulerianCycle[[image], 2]

オイラー閉路を求める：

Wolfram Language code: FindEulerianCycle[[image], All]//Length

規則を使ってグラフを指定する：

Wolfram Language code: FindEulerianCycle[{1 -> 2, 2 -> 3, 3 -> 1, 1 -> 3, 3 -> 4, 4 -> 1}]

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

Wolfram Language code: FindEulerianCycle[[image]]

FindEulerianCycleは大きいグラフに使うことができる：

Wolfram Language code: g = HypercubeGraph[14];
Wolfram Language code: EdgeCount[g]
Wolfram Language code: FindEulerianCycle[g]//Short//Timing

アプリケーション  (7)

ケーニヒスベルクのプレーゲル河に架かる7つの橋を2度通らずすべて1度だけ通ってもとの場所に戻ることはできない：

Wolfram Language code: graph = \!\(\*GraphicsBox[«6»]\);
Wolfram Language code: FindEulerianCycle[graph]

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

Wolfram Language code: g = [image];

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

Wolfram Language code: EulerianGraphQ[g]

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

Wolfram Language code: {s, t} = Pick[VertexList[g], OddQ /@ VertexDegree[g]]
Wolfram Language code: h = Graph[Append[VertexList[g], "z"], Join[EdgeList[g], {t"z", "z"s}], VertexCoordinates -> Append[GraphEmbedding[g], {0., -0.8}], VertexSize -> Tiny, EdgeStyle -> {Dashed, t"z" -> Green, "z"s -> Green}]
Wolfram Language code: EulerianGraphQ[h]

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

Wolfram Language code: FindEulerianCycle[h]//First

頂点 を含む辺が最後になるまでオイラー閉路の辺を回転させる：

Wolfram Language code: NestWhile[Append[#[[2 ;; ]], #[[1]]]&, %, Not[MemberQ[List@@#[[-2]], "z"]] || Not[MemberQ[List@@#[[-1]], "z"]]&]

オイラー路を示す：

Wolfram Language code: Table[HighlightGraph[g, Append[Style[#, Directive[StandardGray, Dashing[{}]]]& /@ %[[ ;; i - 1]], Style[%[[i]], Directive[Red, Dashing[{}]]]]], {i, Length[%] - 2}]

以下の会議に最適な会議室のスケジュールを求める：

同じ会議への出席者を辺で結んだ出席者のグラフ：

Wolfram Language code: g = [image];

1人が連続する2つの会議の両方に出席できるような最適のスケジュールはない：

Wolfram Language code: FindEulerianCycle[g]

出席者間の奇数の仮想会議を加える：

Wolfram Language code: h = EdgeAdd[g, "Michael""William"];
Wolfram Language code: First[FindEulerianCycle[h]]

可能なスケジュール：

Wolfram Language code: TableForm[Apply[List, Rest[%], {1}], TableHeadings -> {Table[i, {i, 10}], None} ]

頂点が長さ(k-1)の部分配列で辺が長さ k の部分配列である，環状ゲノム"ATGGCGTGCA"のグラフに基づいたアセンブリ：

Wolfram Language code: threeMers = StringJoin /@ Partition[Characters["ATGGCGTGCA"], 3, 1, 1]
Wolfram Language code: edges = DirectedEdge[StringDrop[#, -1], StringDrop[#, 1]]& /@ threeMers
Wolfram Language code: Graph[edges, GraphLayout -> "CircularEmbedding", PlotTheme -> "DiagramGold"]

ゲノムを再構築する：

Wolfram Language code: FindEulerianCycle [%]//First
Wolfram Language code: StringJoin[StringTake[First /@ %, 1]]

オイラー閉路から k 分木のde Bruijn系列を構築する：

Wolfram Language code: g = DeBruijnGraph[2, 3]
Wolfram Language code: cycle = First[FindEulerianCycle[g]]

de Bruijn系列：

Wolfram Language code: First[IntegerDigits[# - 1, 2, 3]]& /@ cycle[[All, 1]]

有向オイラー閉路に沿って頂点が訪れられる順番を求める：

Wolfram Language code: Graph[{12, 23, 31, 34, 45, 53, 55}]
Wolfram Language code: FindEulerianCycle [%]//First

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

Wolfram Language code: First /@ %

オランダの風車グラフ(Dutch Windmill graph)のオイラーグラフを求める：

Wolfram Language code: g = GraphData[{"DutchWindmill", {3, 4}}];
Wolfram Language code: edges = First[FindEulerianCycle[g]]

オイラー閉路に沿って訪れた辺にラベルを付ける：

Wolfram Language code: HighlightGraph[g, Table[Labeled[edges[[i]], i], {i, Length[edges]}]]

特性と関係  (6)

オイラーグラフの大規模なコレクションを得るのにGraphDataを使う：

Wolfram Language code: Short[GraphData["Eulerian"]]

非オイラーグラフの大規模コレクションに使う：

Wolfram Language code: Short[GraphData["Noneulerian"]]

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

Wolfram Language code: GraphData[{"DutchWindmill", {2, 4}}]
Wolfram Language code: EulerianGraphQ[%]

頂点が偶次数の連結無向グラフにはオイラー閉路がある：

Wolfram Language code: g = GraphData[{"Antiprism", 4}]
Wolfram Language code: VertexDegree[g]
Wolfram Language code: FindEulerianCycle[g]

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

Wolfram Language code: g = Graph[{12, 23, 31, 34, 45, 53}]
Wolfram Language code: Subgraph[g, #]& /@ {{1, 2, 3}, {3, 4, 5}}

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

Wolfram Language code: g = CompleteGraph[{2, 4}]
Wolfram Language code: {EulerianGraphQ[g], FindEulerianCycle[LineGraph[g]]}

すべての頂点の入次数と出次数が等しい有向グラフにはオイラー閉路がある：

Wolfram Language code: g = Graph[{12, 23, 31, 34, 41, 13}]
Wolfram Language code: {ConnectedGraphQ[g], VertexInDegree[g] == VertexOutDegree[g]}
Wolfram Language code: FindEulerianCycle[g]

おもしろい例題  (1)

オイラー閉路を求める：

Wolfram Language code: g = [image];
Wolfram Language code: Shallow[cycle = First[FindEulerianCycle[g]]]

オイラー閉路を動的にハイライトする：

Wolfram Language code: color[cycles_] := {cycles, cycles[[All, 1]], Style[cycles[[-1, 2]], Yellow]}
Wolfram Language code: Dynamic[HighlightGraph[g, color[cycle[[1 ;; Clock[{1, Length[cycle], 1}, 40]]]]]]
Wolfram Research (2010), FindEulerianCycle, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindEulerianCycle.html （2015年に更新）.

テキスト

Wolfram Research (2010), FindEulerianCycle, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindEulerianCycle.html （2015年に更新）.

CMS

Wolfram Language. 2010. "FindEulerianCycle." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindEulerianCycle.html.

APA

Wolfram Language. (2010). FindEulerianCycle. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindEulerianCycle.html

BibTeX

@misc{reference.wolfram_2026_findeuleriancycle, author="Wolfram Research", title="{FindEulerianCycle}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindEulerianCycle.html}", note=[Accessed: 16-September-2026]}

BibLaTeX

@online{reference.wolfram_2026_findeuleriancycle, organization={Wolfram Research}, title={FindEulerianCycle}, year={2015}, url={https://reference.wolfram.com/language/ref/FindEulerianCycle.html}, note=[Accessed: 16-September-2026]}