著者

菊地 洋右

雑誌

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

巻号頁・発行日

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

---

単純グラフ G のすべての辺を含む路をオイラー路、オイラー路が閉路となっているものをオイラー回路という。オイラー路をもつグラフを semi-eulerian とよび、オイラー回路をもつグラフをオイラーグラフとよぶ。オイラーグラフの特徴付けはグラフ理論の教科書に必ず載っていると言っていいほどよく知られている。オイラーグラフが与えられたときに、オイラー回路の数え上げは #P-完全であることが知られている。本研究は、単純グラフ G がオイラー路をもつとき、重複も抜けもなく、そのオイラー路を列挙するアルゴリズムを提案する。本研究のアルゴリズムではまず Fleury’s Algorithm を用いて単純グラフ G のオイラー路を求める。このオイラー路から順次、オイラー路を求めていくことで列挙を行う。提案するアルゴリズムは、Fleury’s Algorithm を適用した後に、すべてのグラフ的列を 1 つあたり O(m) 時間で列挙する。