ネットワーク理論 Text. Part 3 pp. 57-104 最短路問題 pp.58-84 最大流問題 pp.85-94 Ford法,双対問題とポテンシャル，Bellman方程式とBellman-Ford法 負の費用をもつ閉路がある場合，閉路を含まない場合 最大流問題 pp.85-94 最小費用流問題 pp.95-104 1

大名の最小費用流問題 飛脚が運べる量 （容量） 費用 富士山から江戸まで10単位の氷を送りたい． なるべく安く運ぶにはどうしたらよい？ 2

最小費用流問題の特徴 枝に費用がある それぞれの点での流出（入）量が決まっている sでは-10流出 1では0流出 （10流入） tでは10流出 流出量を関数bで表すと b(s)=-10 b(1)=0, b(2)=0, b(3)=0 b(t)=10 3

最小費用流問題（グラフ理論的定義） 点集合 V 枝集合 E 有向グラフ G=(V,E) 枝の容量 u: E → R+ 枝の費用 c: E → R 流出量関数 b: V → R 目的： 費用の合計が最小となる実行可能フロー ただし， 4

実行可能フローとは？ 以下の条件を満たす実数値関数x:E → R フロー整合条件 （各点における氷の消費・補充 が決まっている） 容量制約と非負制約 （飛脚の運べる量には限界がある） 費用の合計を最小にする実行可能フローを最適フローと呼ぶ 5

閉路消去法（基本的アイディア） 基本的には最大流問題に対するFord-Fulkerson法と同じ 費用の概念が入るので，補助ネットワークの作り方が若干異なる 6

そのときに増加する費用は（1単位あたり）-10 補助ネットワーク（最小費用流版） 5流せるところを 1流している状態 費用は（1単位あたり）10 10(1／5) s 1 元の問題のネットワーク 残余容量1 1からsへあと1流せる そのときに増加する費用は（1単位あたり）-10 -10(1) s 1 補助ネットワーク 10(4) 残余容量4 sから1へあと4流せる そのときに増加する費用は（1単位あたり）10 7

補助ネットワーク s 1 s 1 5流せるところを 5流している状態 10(5／5) 元の問題のネットワーク -10(5) 補助ネットワーク 残余容量0 もう流せない 5流せる 1単位あたりの費用増加は-10 8

補助ネットワーク s 1 s 1 5流せるところを 流していない状態 10(0／5) 元の問題のネットワーク 補助ネットワーク 10(5) 残余容量5 あと5流せる 1単位あたりの費用増加は10 もう流せない 9

練習（黒板使用） （補助ネットワークの作り方） ??(??) 15(5/10) s t s t ??(??) ??(??) ??(??) 10(3/5) 1(5/8) ??(??) ??(??) 1 1 10

練習（黒板使用） （補助ネットワークの作り方） -15(5) 15(5/10) s t s t 15(5) 10(2) 1(3) -1(5) 10(3/5) 1(5/8) -10(3) 1 1 11

負閉路 s t 1 負閉路＝ 補助ネットワークにおいて費用の合計が負となる閉路 負閉路がある限り， 負閉路内のフローを増やすと，費用は減る 増やせるフロー量の上限は，負閉路内の枝の残余容量の最小値 -15(5) s t 15(5) 10(2) 10+1+(-15)=-4 1(3) -1(5) -10(3) 4だけ費用が減る！ 1 12

定理：負の閉路による最適フローの特徴づけ 実行可能フローに対する補助ネットワークにおいて，負閉路が存在しなければ，それは最適フローである 証明は省略 13

閉路消去法（アイディア） 最初は適当な実行可能フローからスタート （実行可能フローの簡単な作り方は後述） 少しずつフローの費用を減らしていく （補助ネットワーク上で負閉路を見つけて，負閉路内の枝の残余容量の最小値だけ，負閉路上のフローを増やす） 負閉路が見つからなくなったら終わり 14

sからtへ直通の枝を作り，費用をべらぼうに大きくする 実行可能フローの簡単な見つけ方 sからtへ直通の枝を作り，費用をべらぼうに大きくする 1京(10／10) 1(0／8) 1 t 10(0／5) s 3(0／2) 6(0／6) 2 3 5(0／8) 2(0／5) では， 閉路消去法を やってみよう sからtへ10単位の氷の流れを作りたい 15

閉路消去法 1 t s 2 3 s 1 2 t 3 1京(10／10) 1(0／8) 10(0／5) 3(0／2) 6(0／6) 5(0／8) 2(0／5) s 1 2 t 3 10(5) 5(8) 3(2) 2(5) 1(8) 6(6) -1京(10) 16

閉路消去法 1 t s 2 3 s 1 2 t 3 1京(5／10) 1(5／8) 10(5／5) 3(0／2) 6(0／6) 5(0／8) -10(5) 5(8) 3(2) 2(5) -1(5) 6(6) -1京(5) 1京(5) 1(3) 2(0／5) 17

閉路消去法 1 t s 2 3 s 1 2 t 3 1京(5／10) 1(5／8) 10(3／5) 3(2／2) 6(0／6) 5(2／8) -10(3) 5(6) -3(2) 2(5) -1(5) 6(6) -1京(5) 1京(5) 1(3) -5(2) 10(2) 2(0／5) 18

閉路消去法 1 t s 2 3 s 1 2 t 3 1京(3／10) 1(7／8) 10(5／5) 3(2／2) 6(0／6) 5(2／8) -10(5) 5(6) -3(2) 2(5) -1(7) 6(6) -1京(3) 1京(7) 1(1) -5(2) 2(0／5) 19

閉路消去法 1 t s 2 3 s 1 2 t 3 1京(0／10) 1(7／8) 10(5／5) 3(2／2) 6(3／6) 5(5／8) -10(5) 5(3) -3(2) 2(2) -1(7) 6(3) 1京(10) 1(1) -5(5) -2(3) -6(3) 2(3／5) 負の閉路が 見つからないので 終了 20

閉路消去法（擬似コード） x:=適当な実行可能フロー while 負閉路がある do 適当な負閉路Cを選択 Δ:=C内の枝の残余容量の最小値 21