スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

混合グラフにおける Euler 閉路

有向 or 無向グラフにおいて、Euler 閉路が存在するかの判定法は有名で、たとえば Spaghetti Source に載っている。

一方で、グラフが混合グラフになると、状況はそれほど簡単ではなくなる。
混合グラフの場合の判定法について、調べたことを記録しておく。

Tags : グラフ理論 プログラミング アルゴリズム

用語

・ 混合グラフ (mixed graph) : 無向辺と有向辺を両方もちうるグラフ
・ Euler 閉路 (Euler cycle, Euler circuit) : グラフのすべての辺を 1 回だけ通る閉路



記号

混合グラフを G = (V, E, A) とおく。
ここで、
V : 頂点集合
E : 無向辺集合
A : 有向辺集合



判定法

連結な混合グラフ G が次の 1. 2. をみたす ⇔ G は Euler 閉路をもつ

1.
すべての頂点の次数 (無向辺による次数 + 有向辺による入次数 + 有向辺による出次数) が偶数である

2.
G からすべての有向辺を取り除いたものを G' とする。 G' = (V, E).
E のすべての辺の重みを 1 とする。
G' に 2 つの頂点 s, t を加える。
s, t と u (∈V) 間の辺を次のように定める。
G における u の入次数を a, G における u の出次数を b とすると、
・ a < b のとき、重み b-a をもつ有向辺 (u, t) を E に加える。
・ a > b のとき、重み a-b をもつ有向辺 (s, u) を E に加える。

このとき、
s-t 最大フロー = s から出る辺の重みの総和 (= t に入る辺の重みの総和)
となる。



なぜこれでいいか

条件 1. が必要なことは当然。

条件 2. では、無向辺をどっち向きに渡るかを決めていることになる。
無向辺をフローが流れる向きの有向辺とみると、次数のバランスが取れるようになっている。
辺 (s, u), (u, t) の重みはこのバランスを考えて決められている。

s-t 最大フロー = s から出る辺の重みの総和
というのは、すべての頂点の次数を調節するために十分な量のフローが流れているということ。



補足

G の連結性が保証されていないときは、それも別途調べないといけない。
次数が 0 でない頂点が連結していればよい。

二部グラフを作って、それが完全マッチングをもつかどうかで判定する方法もあるらしいのだけど、英語が読めなくて理解できなかった。 (ここ)
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。