レポート問題 問題 問題 問題

レポート レポート レポート

レポート問題 問題 問題 問題

問１：下記の図は，最大フロー問題およびその最大フローを表す．

これらのフローに対し，残余ネットワークを書きなさい．

また，授業でやったやり方に従って最小 s-t カットを求めよ

1/3 4/4 5/5

2/2 1/1

s

b a

t

(a)

2 4 5

2 1

s

b a

t

残余ネットワークと最小カット

レポート レポート レポート

レポート問題 問題 問題 問題

問１：下記の図は，最大フロー問題およびその最大フローを表す．

これらのフローに対し，残余ネットワークを書きなさい．

また，授業でやったやり方に従って最小 s-t カットを求めよ

(b)

s

d b

c a

2/3

2/2 1/2

2/2

2/3

1/1 1/1 2/2

1/1

t s

d b

c

a 2

2 1

1 2

1

t

2 1

1 2 1

1

残余ネットワークと最小カット

レポート レポート レポート

レポート問題 問題 問題 問題

1/1 1/3 0/1

1/3 2/4

s

b a

t y_ba/1

0/2

s

b a

y_sb/2 t

図2：残余ネットワークと そのフローy

0/1

y_as/1 y_at/1

y_tb/2 0/2

1-y_ba

0+y_at 1- y_as

1+y_sb 2-y_tb

s

b a

t

図3：新しいフローx’

問2：図１のようなネットワークとフロー x について考える．

このフローに対して，図2のような残余ネットワーク上のフ

ロー y を考えると，図3のような新しいフロー x’ が得られる．

このとき，新しいフローが上下限制約および流量保存条件 を満たすことを証明せよ．（ヒント：残余ネットワーク上のフ ロー y に対する上下限制約および流量保存条件を使う）

図1：与えられた問題と 現在のフローx

レポート レポート レポート

レポート問題 問題 問題 問題

1/1 1/3 0/1

1/3 2/4

s

b a

t y_ba/1

0/2

s

b a

y_sb/2 t

0/1

y_as/1 y_at/1

y_tb/2 0/2

1-y_ba

0+y_at 1- y_as

1+y_sb 2-y_tb

s

b a

t

3/3

1/1 3/4

3/3

0/6 1/2

4/9

d b

c a

g

3/3

4/4 2/2

s 5/5

t

問題3：スライド１７枚目の最大フロー問題を解いて，

供給・需要を満たすフローを求めなさい．

最大フロー

3/3

1/1 3/4

3/3

0/6 1/2

4/9

d b

c a

g

供給・需要を満たすフロー

4 -2

0

-5

問題4：スライド１９枚目の最大フロー問題を解いて，

上下限制約を満たすフローを求めなさい．

1 3

4 4

3 b d

a c 1

-2

-1

2

供給・需要を満たす フローを求める問題

1 3

4 4

3 b d

a c 1

2

1

2

最大フロー問題

s t

問題4：スライド１９枚目の最大フロー問題を解いて，

上下限制約を満たすフローを求めなさい．

0/1 1/3

2/4 0/4

0/3 b d

a c 1

-2

-1

2

供給・需要を満たす フロー

0/1 1/3

2/4 0/4

0/3 b d

a c 1/1

2/2

1/1

2/2

最大フロー

s t

3/[3, 4]

1+1/[1,4]

2+1/[1, 5]

2/[2,6]

1/[1, 4]

b d a c

上下限制約を満たすフロー

問題4：スライド１９枚目の最大フロー問題を解いて，

上下限制約を満たすフローを求めなさい．

応用 応用

応用 応用： ：： ：上下限制約 上下限制約 上下限制約を 上下限制約 を を を満 満 満 満たす たす たす たすフロー フロー フロー フローを を を求 を 求 求 求める める める める

[3, 4]

[1,4]

[1, 5]

[2,6]

[1, 4]

b d a c

入力：有向グラフ

各枝

∈

フローの上限値

下限値

≦

≦

出力：次の条件を満たすフロー

各頂点

∈

での流量保存条件

（

から流出するフロー量）

ー（

に流入するフロー量）＝０ 各枝

の上下限条件

l_ij

≦

≦