演習問題解答例

(1)

演習問題

（１）定式化せよ (a)

2,

2 4,

1 3,

8 2,

5

s b a t

3,

3

4 -4

0

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

(2)

演習問題

（２）初期フローに対する，定理3のポテンシャルの条件を具体的に書け．また，そのようなポテンシャルが存在しない理由を，条件を使って説明せよ． (a)

0

3

1

s b a t

3

初期フロー ௦ ௔ ௔ ௧ ௦ ௕ ௕ ௧ ௔ ௕ 赤枠内の式より 1-8+2≧0 となり矛盾

(3)

演習問題

（3）与えられた初期フローに対して負閉路消去法を適用し，最小費用フローを求めよ（途中の計算過程も省略せず書くこと） (a)

2,

2 1,

1 2,

8 1,

5

s b a t

3,

-3

0

3

1

s b a t

3

初期フロー残余ネットワーク

3,

-1

1,-8 1,-5 負閉路が存在（費用_{-5，容量1）} 閉路に沿ってフローを1流す

(4)

演習問題

(a) 1,2

3,

8 1,

5

s b a t

3,

-3

1

4

0

1

s b a t

3

フロー残余ネットワーク

4,

-1

1,-5 1,-2 負閉路が存在しないので，これは最小費用フロー

(5)

演習問題

(a)

1

4

0

1

s b a t

3

フロー（４）得られた最小費用フローに対し，定理３の条件を満たすポテンシャルを求めよ． ௦ ௔ ௔ ௧ ௦ ௕ ௕ ௧ ௔ ௕ これらの式を満たすポテンシャル（のひとつ）は ௦ ௔ ௕ ௧

(6)

演習問題

（１）定式化せよ

(b)

z c a

₁

3

t b y 枝_{(y, t), (z, t) の容量は３，それ以外の枝の容量は１} t に入る枝の費用は０，それ以外は各枝の数値を参照

2

3

1

1 ₀

0 -3

最小化 _௔௬ _௔௭ _௕௬ _௕௭ ௖௬ ௖௭ 条件 _௔௬ _௔௭ _௕௬ _௕௭ ௖௬ ௖௭ ௬௧ ௔௬ ௕௬ ௖௬ ௭௧ ௔௭ ௕௭ ௖௭ ௬௧ ௭௧ ௔௬ ௔௭ ௕௬ ௕௭ ௖௬ ௖௭ ௬௧ ௭௧

(7)

演習問題

(b)

_{初期フロー} z c a

₀

1

t b y

2

1

0

1

（２）初期フローに対する，定理3のポテンシャルの条件を具体的に書け．また，そのようなポテンシャルが存在しない理由を，条件を使って説明せよ． ௬ ௧ ௭ ௧ ௔ ௬ ௕ ௭ ௖ ௭ ௔ ௭ ௕ ௬ ௖ ௬ 赤枠内の式より 0+0+1-3≧0 となり矛盾

(8)

演習問題

（3）与えられた初期フローに対して負閉路除去法を適用し，最小費用フローを求めよ（途中の計算過程も省略せず書くこと）

(b)

z c a _1,₁ t b y 初期フロー z c a

₀

1

t b y

2

1

0

1

残余ネットワーク負閉路が存在（費用_{-3，容量1）} 閉路に沿ってフローを1流す 1,-3 1,-2 1,1 1,-3 1,2 1,0 2,0 2,0 1,0

(9)

演習問題

(b)

z c a _1,_-1 t b y 初期フロー z c a

₁

0

t b y

2

1

0

1

0

残余ネットワーク負閉路が存在（費用_{-1，容量1）} 閉路に沿ってフローを1流す 1,3 1,-2 1,1 1,3 1,-2 1,0 2,0 2,0 1,0

(10)

演習問題

(b)

z c a _1,_-1 t b y 初期フロー z c a

₁

0

t b y

1

0

2

1

0

残余ネットワーク 1,3 1,2 1,-1 1,3 1,-2 2,0 1,0 1,0 2,0 負閉路が存在しないので，これは最小費用フロー

(11)

演習問題

(b)

_{初期フロー} z c a

₁

0

t b y

1

0

2

1

0

（４）得られた最小費用フローに対し，定理３の条件を満たすポテンシャルを求めよ．これらの式を満たすポテンシャル（のひとつ）は ௔ ௕ ௖ ௬ ௭ ௧ ௬ ௧ ௭ ௧ ௔ ௬ ௕ ௭ ௖ ௭ ௔ ௭ ௕ ௬ ௖ ௬