Network Programming 3
最大フロー問題
始点ｓから終点ｔへのフロー（flow）
条件２：流量保存則
- 各点において （流入するフローの和）＝（流出するフローの和）
例題５-１ 実行可能フロー？
最大フロー問題（定式化）
- ネットワークの流量： 始点ｓから流出するフローの和 目的 ネットワークの流量→最大 条件 実行可能フロー
最大フロー問題の二大基本解法
- ラベリング法（Ford-Fulkerson）
- 簡単な手順の繰り返し．直感的に妥当性が理解できる．計算時間が多くかかる． 改良：Dinicの解法
ラベリング法（準備) 残余ネットワーク
ラベリング法
- 手順２ 増加道がある限り以下を繰り返す．
- 残余グラフで始点ｓから終点ｔまでの道を 見つける．（その道を増加道と呼ぶ)
- 増加道上の枝容量の最小値分のフローを，増加道に沿って流す．
例題５-２ ラベリング法
PPT Slide
PPT Slide
PPT Slide
演習５-１ 最大フローを求めよ
演習５-２
- 演習５-１のネットワークにおいて，始点ｓから終点ｔへもっと多くのものを流すには，どの枝の容量を大きくするのが効果的か考えなさい．
ラベリング法の欠点
例題５-３ 流せるか？
例題５-4 Shall we dance?
社交ダンスパーティーに男性・女性５人ずつ集まった．
幹事がアンケートをとったところ，パートナーになってもよいと
お互い思っているペアは以下の組合せであることがわかった．
マッチング問題の解法
- 「フローが流れている元の枝⇔マッチング」 なぜか？
演習５-４ 最大マッチングを求めよう
演習５-５ バス会社運行係
また，各ターミナル間の回送に要する時間は右の通りである．