著者

菊地 洋右

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.7, pp.1-4, 2010-09-15

参考文献数

2

---

単純グラフ G のすべての辺を含む路をオイラー路、オイラー路が閉路となっているものをオイラー回路という。オイラー路をもつグラフを semi-eulerian とよび、オイラー回路をもつグラフをオイラーグラフとよぶ。オイラーグラフの特徴付けはグラフ理論の教科書に必ず載っていると言っていいほどよく知られている。オイラーグラフが与えられたときに、オイラー回路の数え上げは #P-完全であることが知られている。本研究は、単純グラフ G がオイラー路をもつとき、重複も抜けもなく、そのオイラー路を列挙するアルゴリズムを提案する。本研究のアルゴリズムではまず Fleury's Algorithm を用いて単純グラフ G のオイラー路を求める。このオイラー路から順次、オイラー路を求めていくことで列挙を行う。提案するアルゴリズムは、Fleury's Algorithm を適用した後に、すべてのグラフ的列を 1 つあたり O(m) 時間で列挙する。For simple graph G, eulerian trail is a trail that has all edges in G. If eulerian trail is close circuit, it is called eulerian circuit. If G has a eulerian trail, G is called semi-eulerian and if G has a eulerian circuit, then G is eulerian graph. A characterization of eulerian graph is well-known and may appear in any graph theory. Given eulerian graph, counting eulerian circuits is #P¡complete. This paper will propose an algorithm to generate all eulerian trail for simple graph G, if such trail exists. At first, we obtain the minimum eulerian trail of G, applying Fleury's algorithm. Next, we generate all eulerian trails. Our algorithm generates all eulerian trails in O(m2) for each, after applying Fleury's algorithm, where m is the number of edge in G.