第７回組合せ最適化輪講
2.4 オイラーグラフと２部グラフ
田部井 靖生
概要
•
•
•
•
•
•
オイラーウォークとオイラーグラフ
２つの関係の定理
オイラーウォークを見つけるアルゴリズム
グラフをオイラーグラフに変化する方法
奇数ジョインと奇数カバー
２つの関係の定理
２部グラフとその定理
定義 2.23
• グラフGのすべての辺を含む閉じたウォークを
オイラーウォークという
• 無向グラフGはすべての点の次数が偶数であ
るとき、オイラーであると呼ばれる
• 有向グラフGはすべての点v∈V(G)で|δ(v)|=|δ+(v)|であるときオイラーであると呼ば
れる
定理2.24
(有向あるいは無向)連結グラフGがオイラー
ウォークをもつための必要十分条件は、Gがオ
イラーであることである
（証明）
必要性 ⇨
オイラーウォークに k回現れる途中の点の次数
は2kである
• 十分性 ⇐
1)W=v1,e1,v2,…,vk,ek,vk+1を最長のウォークとする
2)最長ウォークWはVk+1から出て行く辺をすべて
含むことになり、Gがオイラーであることより、
v1=vk+1となり、Wは閉ウォーク
Wがオイラーウォークなることの証明
3)Wに含まれない辺が存在すると仮定する
4) Gは連結なので、Wに含まれない辺で少なく
とも一方の端点がWに含まれるような辺eが存
在する
5) EをWにつなげるとWよりも長いウォークがで
きてしまう！(矛盾)
6) Wはすべての辺を含むオイラーウォークとな
る
アルゴリズム2.3 Eulerのアルゴリズム
•
•
-
入力：無向連結グラフ
出力：GのオイラーウォークW
基本は再帰アルゴリズム
毎回の再帰呼び出しでは、閉ウォークWを見
つける ②と③
- Wのそれぞれの点に対して、再帰呼び出し
定理 2.25
Eulerのアルゴリズムは正しく動作する
証明)
オイラーグラフGと点v1∈V(G)に対して
Euler(G,v1)が呼び出されると、v1を含むGの連
結成分G1のオイラーウォークが返されることを、
|E(G)|についての帰納法で証明する
• Base case: E(G)=φのとき自明
• Inductive step E(G)≠φのとき
1)④で返されるパスWは閉ウォークであり、すべて
の辺を含んでいるならば終了.そうでないとき、閉
ウォークをG1とする
2)そうでないとき、Gから②で辺が取り除かれたグ
ラフG’はオイラーグラフである
3)④でW上の辺eのなかで、一方がG’の点であるも
のをvi(i=2,…,k)とする
4)帰納法の仮定より、eはWiに属する
5)⑤で構成されるウォークはG1のオイラーウォーク
になる
定義
Gを無向グラフとして、FをV(G)の非順序対の族
とする。このとき、(V(G),E(G)∪F)がオイラーなら
ば、Fは奇数ジョインという
e4
e1
e3
e2
e1
e3
e2
F={e4}
定義
Gから各e∈Fを順次縮約していって得られるグラ
フがオイラーならば、Fは奇数カバーと呼ばれる
e4
e1
e3
e2
F={e4}
e3
e1
e2
定理 2.26
無向グラフに対して、以下の(a), (b)が成立する
(a)奇数ジョインは奇数カバー
(b)極小な奇数カバーは奇数ジョイン
a)の証明
偶数+偶数=偶数
偶数+奇数=奇数
奇数+奇数=偶数
1) Fを奇数ジョインとする
2) GからFを縮約して得られるグラフをG’とする
3) Fが奇数ジョインなので(V(G),F)の各連結成
分Xは奇数次数の点を偶数個もつ
4) Fが奇数ジョインであるので、点v∈V(G)が
(V(G),F)で奇数次数であることと点vがGで奇数
次数であることは等価
5) (V(G),F)の各連結成分Xに含まれるGの奇数
次数の点も偶数個となり、|δG(X)|は偶数
6) グラフ G’は偶数次数の点しかないことになり、
Fは奇数カバーになる
• 定義
無向グラフGの２分割とは、AとBで誘導されるG
の部分グラフがそれぞれ空となるような点集合
の分割V(G)=A∪Bである
Gは２分割をもつとき、２部グラフと呼ばれる
A
B
• V(G)=A∪B, |A|=n,|B|=m,
E(G)={{a,b}:a∈A,b∈B}
となるような単純２部グラフGをKn,mと書き、完全
２部グラフという
定理 2.27
無向グラフGが２部グラフであるための必要十
分条件は、Gが奇数長の閉路をもたないことで
ある。
必要性 ⇨
1)Gを２分割V(G)=A∪Bをもつ２部グラフとし、
v1,e1,v2,…,vk,ek,vk+1をGの閉路とする。
2)vi∈Aであることとiが奇数であることは等価
3)さらに、vk+1=v1∈Aなのでk+1は偶数
• 十分性 ⇐
任意にv∈V(G)を選んで、(G,s)に幅優先探索を適用
してsからすべての点v∈V(G)への距離をもとめる。T
を得られる幅優先探索木とする
A:={v∈V(G): distG(s,v)は偶数}, B:=V(G)\A
A1
B1
A1
B3
B2
A2
A3
G[A]あるいはG[B]に辺e={x,y}が存在すれば、Tでの
x-yパスにeをつなげて奇数閉路が得られる
そのような辺がなければ２分割となる
© Copyright 2024 ExpyDoc
