辺連結度

Applications of
Network Flow
目次


マッチング
辺連結度
ネットワークフローの応用１
マッチング
２部グラフにおける最大マッチング問題を
ネットワークフロー問題を利用して解く
方針
２部グラフG (部集合：P,J)
 ２つの新たな頂点s,tを追加
 sから∀p∈Pへの辺，∀ j∈Jからtへの辺を追加
 ネットワーク内の各辺の容量を１
このネットワークの最大整数フローをQと置く
P
J
J
P
s
t
J
P
s
t
最大フロー Q
J
P
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
s
1
1
1
1
1
1
1
1
1
1
t
最大フロー Q
J
P
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
s
1
1
1
1
1
1
1
1
1
1
t
最大マッチング
目次


マッチング
辺連結度
ネットワークフローの応用２
辺連結度
辺連結度を求める組み合わせ問題を
ネットワークフロー問題を利用して解く
辺連結度
G:グラフ
辺連結度：
Gから取り除くとGが連結でなくなる辺の
最小本数
Ｇ
Ｇ
Ｇ
Ｇ
辺連結度２
辺連結度
ある頂点vに接続している辺をすべて取り
除くと，必ずグラフは連結でなくなる
⇒
辺連結度はグラフの頂点の最小次数を
超えることはない
辺連結度
辺連結度が最小次数よりはるかに小さい場合
がある
グラフが橋を持つ場合など
。
辺連結度=１
方針
G：頂点数Vのグラフ
∀j=2,・・・,V-1について
ネットワークフロー問題を解く
（全部でV-1回解く）
方針




ある頂点jを１つ固定する。
Gの頂点１を入り口とし、頂点jを出口とするネット
ワークXjを考える。
Gの各辺をXjでは反対向きの２つの辺で、容量がそ
れぞれ１であるようなものと置き換える。
Xjのネットワークフロー問題を解いて、最大フロー
Q(j)を求める
Q(j)の最小値がGの辺連結度
a
b
e
c
d
a ←1
b
e
c
d ←j
a ←1
b
e
c
d ←j
a ←1
b
e
c
d ←j
a ←1
b
e
c
d ←j
a ←1
b
e
c
d ←j
a ←1
各辺の容量=１
b
e
c
d ←j
a ←1
各辺の容量=１
b
e
c
d ←j
a ←1
各辺の容量=１
b
e
c
d ←j
a ←1
各辺の容量=１
b
e
c
d ←j
a ←1
各辺の容量=１
b
e
c
d ←j
a ←1
各辺の容量=１
b
e
c
d ←j
最大フロー=４
a ←1
各辺の容量=１
４ b
e ４
c
４
d
４
a ←1
各辺の容量=１
４ b
e ４
c
４
d
４
辺連結度=４

Download Report