講義資料

今日の講義で学ぶこと
2/11
• マッチング（復習）
グラフとネットワーク（13）
– マッチング問題 (matching problem)
– Hall の定理
～最大マッチング～
• 最大フローと最大マッチング
• 最大フローのアルゴリズム(次回)
最大マッチング（復習）
(Maximum Matching Problem)
3/11
【定義】与えられた2部グラフ G = (V1,V2,E)
上で、次の条件を満たす辺集合 M ⊆ E を
マッチング(matching)と呼ぶ。
{(ui , v j ) | v j ∈ V 2 } ≤ 1 for ∀ui ∈ V 1
{(ui , v j ) | ui ∈ V 1 } ≤ 1 for ∀v j ∈ V 2
特に、位数最大となるマッチングを見出す
問題を最大マッチング問題と呼ぶ。
完全マッチング問題（復習）
(perfect matching problem)
4/11
【定義】与えられた2部グラフ G = (V1,V2,E)
は、|V1| = |V2| = n であるとする。M ⊆ E を
マッチングとするとき、|M| = n を満たす
マッチングがあるかどうかを判定する問題
を完全マッチング問題と呼ぶ
【注】完全マッチングが存在するかどうかを判定
するためには、最大マッチング M をもとめて、
|M| = n が成立するかどうかをチェックすれば良い
【注】位数 = グラフの頂点数、サイズ = グラフの辺数
5/11
【最大マッチングの例】
a
e
b
f
c
g
d
h
a-g
b-h
c-f
マッチングの存在判定と構成
6/11
• Hallの定理（第10回講義参照）
– 存在判定
– 必要十分条件を与えている
– 条件をチェックのアルゴリズムはクラスNP
– マッチングを得るための構成的手法ではない
• 最大マッチングを構成する手法
d-e
最大マッチングかつ完全マッチング
– 増大道を利用する（ハンガリー法）
– 最大フロー問題を利用する
多項式時間（クラスP）
アルゴリズム
最大フローと最大マッチング
V1
E
7/11
V2
s
【練習問題】始点 s から終点 t への最大フロー 8/11
を求めなさい。ただし、初期状態では、全ての
有向辺でフローは 0 とせよ。 (フローの整数性参照)
t
 辺 E を V1 から V2 への有向辺に変える
 与えられた2部グラフに始点 s と終点 t を加える
 s から V1、V2 から t への有向辺を加える
 辺は容量を 1 としたネットワーク NG の最大フローを
考える
 最大フローで 1 となった E の辺が最大マッチング
9/11
10/11
【補足】追加ネットワークが以下ではなぜダメ？ 11/11
12/18
a
1/1
0/1
s
1/1
1/1
1/1
e
1/1
b 1/1
f
1/1
0/1
t
1/1
c
d
1/1
1/1
g
h
P1 = saht Δ 1 = 1 P2 = scgt Δ 2 = 1 P3 = sdet Δ 3 = 1
このときの残余ネットワークを求めると
a
e
1
1
s
b
f
1
1
1
t
1
c
g
d
h
お知らせ
1
1
(s,t)-路がまだ存在する
P = sbhagcft
第12回 1月14日（木）
第13回第1月18日（月）
第14回 1月25日（月）
第15回 2月１日（月）演習のみ
第16回 2月８日（月）期末試験

Download Report