---
title: 【しっかり学ぶ数理最適化】4.3.3
tags: 
author: [京都大学人工知能研究会KaiRA](https://convert.docswell.com/user/kyoto-kaira)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/4JM9NWZVEW.jpg?width=480
description: 【しっかり学ぶ数理最適化】4.3.3 by 京都大学人工知能研究会KaiRA
published: December 25, 25
canonical: https://convert.docswell.com/s/kyoto-kaira/KLVM94-2025-12-25-211646
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/4JM9NWZVEW.jpg)

2025 年後期輪読会 #10 (12/25)
しっかり学ぶ数理最適化
4.3.3 ネットワークフロー
京都大学 工学部 情報学科
宮前明生
0


# Page. 2

![Page Image](https://bcdn.docswell.com/page/PJRGDY6WE9.jpg)

アジェンダ
◼ 最大流問題
◼ 最小費用流問題
1


# Page. 3

![Page Image](https://bcdn.docswell.com/page/PEXX1GMVEX.jpg)

アジェンダ
◼ 最大流問題
◼ 最小費用流問題
2


# Page. 4

![Page Image](https://bcdn.docswell.com/page/3EKW24G5ED.jpg)

最大流問題：最大流問題とは
前提
• 入口となる頂点𝑠と出口となる頂点𝑡が存在する
• 辺には流量𝑥𝑒 と容量𝑢𝑒 が定義される（整数）
• 入口から出口に流れるフローの総量𝑓を最大化する問題
条件
1. 入口𝑠について、流出する総量から流入する総量を引くとフローの総量𝑓
2. 入口𝑠と出口𝑡を除いた頂点𝑣について、流出する総量と流入する総量は等しい
3. 出口𝑡について、流出する総量から流入する総量を引くとフローの総量−𝑓
3


# Page. 5

![Page Image](https://bcdn.docswell.com/page/L7314LN1J5.jpg)

最大流問題：増加路法
残余ネットワークは以下の容量を持つ有向グラフ
•
•
頂点𝑢から頂点𝑣に流せるフローの残り容量𝑢𝑒 − 𝑥𝑒 、これは頂点𝑢から頂点𝑣の方向
頂点𝑣から頂点𝑢に押し戻せるフローの残り容量𝑥𝑒 、これは頂点𝑣から頂点𝑢の方向
増加路とは、残余ネットワークで入口から出口までの方向に流れる経路
増加路法
1. 残余ネットワークの増加路があるか探す（なければ終了）
2. 見つけた増加路上で可能な限りフローを増加させる
4


# Page. 6

![Page Image](https://bcdn.docswell.com/page/87DXQNWKEG.jpg)

最大流問題：増加路法の実行例
5


# Page. 7

![Page Image](https://bcdn.docswell.com/page/VJPPL593J8.jpg)

最大流問題：増加路法の計算量と最小カット問題
増加路法の計算量
流量𝑥𝑒 と容量𝑢𝑒 が整数なので、1回の反復で少なくとも流量は1増える
容量𝑢𝑒 の最大値を𝑈とすると、頂点𝑠から出る辺の数は高々|𝑉| − 1、フローの最大量は(|𝑉| − 1)𝑈、
反復回数の上限も(|𝑉| − 1)𝑈回
• 深さ優先探索や幅優先探索を用いれば、増加路は𝑂(|𝑉| + |𝐸|)で求められる。計算量は𝑂(|𝑉||𝐸|𝑈)
最小カット問題
•
•
• 頂点集合𝑉を𝑆と𝑇に分割し、 𝑆から𝑇への容量を最小化する問題
最大フロー最小カット定理
・最大フローの量と最小カットの容量は等しい
6


# Page. 8

![Page Image](https://bcdn.docswell.com/page/2EV2QPMNEQ.jpg)

最大流問題：最大流問題の応用①2部グラフのマッチング問題
2部グラフのマッチング問題
• 2部グラフの頂点間で、頂点を重複させずに最大何本の辺（ペア）を結べるか
2部グラフのマッチング問題から最大流問題へ
• 2部グラフに入口𝑠と出口𝑡を追加し、 𝑠から全ての𝑉1 への辺と全ての𝑉2 から𝑡への辺を追加
• 辺の容量は全て1とすると、最大流問題とみなせる
2部グラフのマッチング問題の計算量
• 入口𝑠から出口𝑡へのフローの総量はマッチングの本数と同じ（高々min{|𝑉1 |, |𝑉2 |}）
• 深さ優先探索や幅優先探索を用いれば、増加路は𝑂(|𝑉| + |𝐸|)で求められる。計算量は𝑂(|𝑉||𝐸|)
7


# Page. 9

![Page Image](https://bcdn.docswell.com/page/57GRWPG5EL.jpg)

最大流問題：最大流問題の応用②画像分割
画像分割問題
• 画像を解析したい対象𝐹と
ത
それ以外の背景𝐹に分割する問題(𝐹,
𝐹ത ⊂ 𝑉)
画像分割問題から最小カット問題へ
ത
• 対象𝐹に属する尤度をℓ𝑣 、背景𝐹に属する尤度を
ℓ𝑣 、
隣接する画素の組{𝑢, 𝑣}について分離ペナルティを
𝑝𝑢𝑣 とする
• 𝐿 = σ𝑣𝜖𝑉(ℓ𝑣 + ℓ𝑣 )、𝜑(𝜎𝑢 , 𝜎𝑣 )は𝑢と𝑣が異なる領域で
あれば1, 同じ領域であれば0
max: σ𝑣𝜖𝐹 ℓ𝑣 + σ𝑣𝜖 𝐹ത ℓ𝑣 − σ{𝑢,𝑣}𝜖 𝐸 𝑝𝑢𝑣 𝜑(𝜎𝑢 , 𝜎𝑣 )
max: 𝐿 − σ𝑣𝜖𝐹 ℓ𝑣 − σ𝑣𝜖 𝐹ത ℓ𝑣 − σ{𝑢,𝑣}𝜖 𝐸 𝑝𝑢𝑣 𝜑(𝜎𝑢 , 𝜎𝑣 )
min: σ𝑣𝜖𝐹 ℓ𝑣 + σ𝑣𝜖 𝐹ത ℓ𝑣 + σ{𝑢,𝑣}𝜖 𝐸 𝑝𝑢𝑣 𝜑(𝜎𝑢 , 𝜎𝑣 )
ത
• これは𝐹と𝐹の最小カット問題とみなせる
8


# Page. 10

![Page Image](https://bcdn.docswell.com/page/4EQV32XLJP.jpg)

アジェンダ
◼ 最大流問題
◼ 最小費用流問題
9


# Page. 11

![Page Image](https://bcdn.docswell.com/page/KJ4M1L65E1.jpg)

最小費用流問題：最小費用流問題とは
最小費用流問題
• 入口となる頂点𝑠と出口となる頂点𝑡が存在しない代わりに、
頂点𝑣から流出するフローの量𝑏𝑣 が与えられる（ 𝑏𝑣 ∈ ℝ、σ𝑣𝜖𝑉 𝑏𝑣 = 0）
• 辺には流量𝑥𝑒 と容量𝑢𝑒 と費用𝑐𝑒 が定義される（整数）
• フローの総費用を最小化する問題
10


# Page. 12

![Page Image](https://bcdn.docswell.com/page/LE18GLV27G.jpg)

最小費用流問題：負閉路消去法
残余ネットワーク
• 頂点𝑢から頂点𝑣に流せるフローの残り容量𝑢𝑒 − 𝑥𝑒 、これは頂点𝑢から頂点𝑣の方向、費用は𝑐𝑒
• 頂点𝑣から頂点𝑢に押し戻せるフローの残り容量𝑥𝑒 、これは頂点𝑣から頂点𝑢の方向、費用は−𝑐𝑒
負閉路とは、経路に沿ってフローを流せば総費用を減らせる経路
負閉路消去法
1. 実行可能なフローを求める（右の図のような 𝑏𝑠 = 0、辺の費用は全て∞の頂点𝑠 を導入）
2. 残余ネットワークの負閉路があるか探す（なければ終了）
3. 見つけた負閉路上で可能な限りフローを減少させる
11


# Page. 13

![Page Image](https://bcdn.docswell.com/page/GEWZKVL2E2.jpg)

最小費用流問題：負閉路消去法の実行例
12


# Page. 14

![Page Image](https://bcdn.docswell.com/page/47Z1Z4M4J3.jpg)

最小費用流問題：負閉路消去法の計算量と最短路繰り返し法のための双対問題
負閉路消去問題の計算量
• 流量𝑥𝑒 と容量𝑢𝑒 と費用𝑐𝑒 が整数なので、1回の反復で少なくとも経路費は1減る
• 容量𝑢𝑒 の最大値を𝑈、費用𝑐𝑒 の最大値を𝐶とすると、辺の数は|𝐸|、反復回数の上限も|𝐸|𝐶𝑈回
• ベルマン・フォード法を用いれば、負閉路は𝑂(|𝑉||𝐸|)で求められる。計算量は𝑂 𝑉 𝐸 2 𝐶𝑈
各制約条件に対応する重み係数𝑧𝑒 , 𝑦𝑣 を導入して、ラグランジュの緩和問題を考えると
𝑚𝑖𝑛: ෍ 𝑐𝑒 𝑥𝑒 + ෍ 𝑧𝑒 𝑥𝑒 − 𝑢𝑒 + ෍ 𝑦𝑣
𝑒∈𝐸
𝑒∈𝐸
𝑒∈𝛿 + 𝑣
𝑣∈𝑉
𝑚𝑖𝑛: − ෍ 𝑏𝑣 𝑦𝑣 − ෍ 𝑢𝑒 𝑧𝑒 +
𝑣∈𝑉
𝑒∈𝐸
෍ 𝑥𝑒 − ෍ 𝑥𝑒 − 𝑏𝑣
෍
𝑠. 𝑡. 𝑥𝑒 ≥ 0, 𝑒 ∈ 𝐸
𝑒∈𝛿 − 𝑣
𝑥𝑒 𝑐𝑒 + 𝑦𝑢 − 𝑦𝑣 + 𝑧𝑒 𝑠. 𝑡. 𝑥𝑒 ≥ 0, 𝑒 ∈ 𝐸
𝑒= 𝑢,𝑣 ∈𝐸
𝑚𝑖𝑛: − ෍ 𝑏𝑣 𝑦𝑣 − ෍ 𝑢𝑒 𝑧𝑒 𝑠. 𝑡. −𝑦𝑢 + 𝑦𝑣 − 𝑧𝑒 ≤ 𝑐𝑒 , 𝑒 = 𝑢, 𝑣 ∈ 𝐸,
𝑣∈𝑉
𝑥𝑒 ≥ 0, 𝑒 ∈ 𝐸
𝑒∈𝐸
• 変数𝑦𝑣 を頂点𝑣のポテンシャルと呼ぶ
• 𝑐ഥ𝑒 (𝒚) = 𝑐𝑒 + 𝑦𝑢 − 𝑦𝑣 を被約費用と定義する
෪𝑣 (𝒙) = 𝑏𝑣 − σ + 𝑥𝑒 + σ𝑒∈𝛿 − 𝑣 𝑥𝑒 を流量保存制約の違反量と定義する
• 𝑏
𝑒∈𝛿 𝑣
13


# Page. 15

![Page Image](https://bcdn.docswell.com/page/YJ6LZ3NGEV.jpg)

最小費用流問題：最短路繰り返し法
相補性定理から以下のような性質が導かれる
性質
最小費用流問題の実行可能なフロー𝒙* が最適である必要十分条件は、残余ネットワークの全ての
辺𝑒 = 𝑢, 𝑣 ∈ 𝐸に対して、 𝑐ഥ𝑒 (𝒚) = 𝑐𝑒 + 𝑦𝑢 − 𝑦𝑣 ≥ 0となるポテンシャル𝒚∗ が存在することである
最短路繰り返し法
1. 𝑐𝑒 ≥ 0ならば𝑥𝑒 = 0、 𝑐𝑒 &lt; 0ならば𝑥𝑒 = 𝑢𝑒 、 𝑦𝑣 = 0とする
∗
2. 𝑏෪
𝒗∗ (𝒙) &gt; 0となる頂点𝑣 を選ぶ（なければ終了）
3. 辺の長さを被約費用𝑐ഥ𝑒 (𝒚)として、頂点𝑣 ∗ から各頂点𝑣への最短路の長さ𝑓𝑣 ∗𝑣 を求める
4. 各頂点𝑣のポテンシャルを𝑦𝑣 = 𝑦𝑣 + 𝑓𝑣 ∗𝑣 と更新する
∗
5. 𝑏෪
𝒗∗ (𝒙) &lt; 0となる頂点𝑣を選び、頂点𝑣 から頂点𝑣への最短路で可能な限りフローを増加させる
14


# Page. 16

![Page Image](https://bcdn.docswell.com/page/GJ51WL5X74.jpg)

最小費用流問題：最短路繰り返し法の実行例
15


# Page. 17

![Page Image](https://bcdn.docswell.com/page/LE314LN475.jpg)

最小費用流問題：最短路繰り返し法の計算量
最短路繰り返し法の計算量
෪𝑣 , 0}は1
• 流量𝑥𝑒 と容量𝑢𝑒 と費用𝑐𝑒 が整数なので、1回の反復で少なくとも超過の総量σ𝑣∈𝑉 max{𝑏
減る
෪𝑣 , 0} ≤ (|𝑉| + |𝐸|)𝑈より反復回数の上限は𝑂(|𝐸|𝑈)
• 容量𝑢𝑒 の最大値を𝑈とすれば、 σ𝑣∈𝑉 max{𝑏
• ダイクストラ法を用いれば、最短路は𝑂(|𝐸| + |𝑉|log|𝑉|)で求められる。
• 計算量は𝑂((|𝐸| + |𝑉|log|𝑉|)|𝐸|𝑈)
16


# Page. 18

![Page Image](https://bcdn.docswell.com/page/8EDXQNW5JG.jpg)

最小費用流問題：最小費用流問題の応用①割当問題
割当問題
• 学生集合𝑉1 とクラス集合𝑉2 のような2部グラフを考える
• 学生𝑖からクラス𝑗への満足度𝑝𝑖𝑗 を辺の重みと考える
割当問題から最小費用流問題へ
• 入口𝑠 (𝑏𝑠 = 𝑚)と出口𝑡 (𝑏𝑠 = −𝑚)を導入する(𝑚 = |𝑉1 |)
• 𝑠から各𝑉1 への容量は1、費用は0、 𝑉1 から𝑉2 への容量は1、費用は−𝑝𝑖𝑗
各𝑉2 から𝑡への容量は𝑢𝑗 、費用は0の最小費用流問題とみなせる（ 𝑢𝑗 はクラス𝑗の上限人数）
17


