演習問題解答例

(1)

演習問題

問1：次の２つの最大流問題に対する定式化を書きなさい

3

5

4

2

1

s b a t

(a)

_(b)

s d b c a

3

2

3

1

3

t 問2：次の２つの最大流問題に対して，増加路アルゴリズムで最大流を求めよ（各反復での残余ネットワークやフローを省略せずに書くこと）問3：2つのグラフの最小カット（と思われるカット）を求めよ（頑張って探してみてください）

(2)

3

5

4

2

1

s b a t

(a)

最大化条件 _௦௔ _௦௕ ௔௧ ௕௧ ௔௧ ௦௔ ௕௔ ௕௧ ௕௔ ௦௕ ௦௔ ௦௕ ௕௔ ௔௧ ௕௧

(3)

3

5

4

2

1

s b a t

(a)

フロー残余ネットワーク

0

s b a t フロー増加路satに沿ってフローを４流すことができる

0

4

0

s b a t

₃

4

2

1

s b a t

1

4

フロー増加路sbtに沿ってフローを1流すことができる

(4)

(a)

フロー残余ネットワークフロー増加路sbatに沿ってフローを1流すことができる

0

4

1

s b a t

₃

4

1

s b a t

1

4

フロー増加路が存在しないので，現在のフローは最大フロー

1

5

4

2

1

s b a t

4

1

s b a t

5

2

1

2

(5)

(b)

s d b c a

3

2

3

1

3

t 最大化条件 _௦௔ _௦௕ ௖௧ ௗ௧ ௔௖ ௦௔ ௕௔ ௕௔ ௕ௗ ௦௕ ௖௧ ௖ௗ ௔௖ ௗ௧ ௖ௗ ௕ௗ ௦௔ ௦௕ ௕௔ ௔௖ ௕ௗ ௖ௗ ௖௧ ௗ௧

(6)

(b)

0

フロー増加路sactに沿ってフローを2流すことができる s d b c a t s d b c a

3

2

3

1

3

t

0

(7)

(b)

0

2

フロー増加路sbdtに沿ってフローを1流すことができる s d b c a t s d b c a

3

2

1

3

t

0

2

0

2

0

2

(8)

(b)

1

2

フロー増加路sbacdtに沿ってフローを1流すことができる s d b c a t s d b c a

3

2

1

2

t

1

2

0

2

1

0

2 1 1

1

(9)

(b)

1

3

s d b c a t s d b c a

2

1

t

2

1

2

1

3

2

1

フロー増加路が存在しないので，現在のフローは最大フロー

(10)

レポート問題

3

5

4

2

1

s b a t

(a)

_(b)

s d b c a

3

2

3

1

3

t 問3：2つのグラフの最小カット（と思われるカット）を求めよ解答例：最小カットは複数あります