フロー・マッチング・カットへ帰着する

概要

仕事を受け手へ割り当てるとき、空いている相手を順に選ぶだけでは、後の仕事の行き先がなくなることがある。以前の割当を付け替えながら選択を増やす仕組みが、フローの残余グラフである。

この単元では、一つの割当模型から、選択を表すマッチング、使用回数を制限する容量、割当を妨げるカットを読み取る。まず元の選択と流れの対応を作り、その後で「何を判定・最適化したいか」に合う下位単元へ進む。

考え方

二仕事の割当を流れにする

仕事を p,qp,q、受け手を a,ba,b とする。pp は a,ba,b のどちらにも、qq は aa だけに任せられる。各仕事は一人へ任せ、各受け手が担当できる仕事は高々一つとする。

仕事を左側、受け手を右側の頂点とし、許可された組にだけ左から右へ辺を張る。これは二部グラフであり、端点を共有しない辺の集合がマッチングである。選んだ辺がそのまま割当になる。

さらに、仕事を送り出す始点(source)ss と、受け取った仕事を集める終点(sink)tt を加え、次の有向辺をすべて容量1で置く。容量は、その辺を通せる流量の上限を表す。

辺表す制約
s→ps\to p、s→qs\to q各仕事を高々一回選ぶ
p→ap\to a、p→bp\to b、q→aq\to a許可された相手へだけ割り当てる
a→ta\to t、b→tb\to t各受け手は高々一仕事を担当する

各辺に容量以下の非負の流量を置き、s,ts,t 以外の頂点では流入量と流出量を等しくする。これが流量保存である。この模型では、ss から出る総流量が割り当てた仕事数になる。例えば s→p→a→ts\to p\to a\to t に1を流すと、「仕事 pp を受け手 aa に任せる」を表せる。

逆辺で以前の選択を取り消す

先に pp を aa に任せると、qq の唯一の候補 aa は使用済みになる。しかし pp を bb へ移せば、aa を qq に空けられる。この付け替えを表すため、現在の流れに対して残余グラフを作る。

元の辺に容量 cc、現在の流量 ff があるとき、順方向にはあと c−fc-f だけ追加でき、逆方向には ff だけ取り消せる。正の残余容量を持つ向きをたどって、ss から tt へ流量を増やす道を探す。先ほどの流量1の状態では、次の道を使える。

s→q→a→p→b→ts\to q\to a\to p\to b\to t

道の各辺の残余容量は1なので、1だけ増やす。元の辺への変更として読むと、次の操作になる。

  • q→aq\to a に1を追加する。
  • 残余辺 a→pa\to p を使って、元の辺 p→ap\to a の流量を1から0へ戻す。
  • p→bp\to b に1を追加する。

あわせて s→qs\to q と b→tb\to t に1を追加する。s→ps\to p と a→ta\to t は1のままで、変更後も各内部頂点の流量保存と容量制約を満たす。元の割当へ戻すと pp は bb、qq は aa を担当先とし、総流量は1から2へ増えた。

逆辺 a→pa\to p は、受け手から仕事へ新たに割り当ててよいという許可ではない。 すでに選んだ p→ap\to a を取り消すための辺である。以前の選択を固定せず、取り消しと追加を一つの道の上で組み合わせることが、貪欲な割当から進むための要点になる。

割当と整数流を両方向に対応させる

全仕事を割り当てた解があれば、各「仕事→担当先」に対応する s→仕事→受け手→ts\to\text{仕事}\to\text{受け手}\to t に1を流す。仕事の重複も受け手の重複もないため、容量制約と流量保存を満たし、全仕事数の流量を得られる。

逆に、仕事数を nn とし、総流量 nn の整数流が得られたとする。ss から各仕事へ出る辺は nn 本・容量1なので、すべてに1が流れる。各仕事では流量保存により許可辺へ合計1が流れ、各辺の流量が整数だから、ちょうど一本が1になる。その辺を担当先として選べばよい。受け手から tt への容量1により、二仕事が同じ受け手を使うこともない。

したがって、全仕事を割り当てられることと、流量 nn の整数流が存在することは同値である。分数の流量では一仕事を複数の相手へ分けてしまうため、この復元には整数性が必要になる。整数容量なら整数の最大流を得られるので、最大流量が nn かを調べれば判定できる。整数性と最大性の一般的な証明は最大流・最小カットへ、割当専用の増加路は二部matching・Hall・Kőnigへ進む。

割当を妨げる容量をカットで見る

今度は許可辺 p→bp\to b を消し、両仕事の候補を aa だけにする。受け手 bb が空いていても、そこへ割り当てる許可がなく、a→ta\to t の容量1が二仕事の通過を妨げる。

頂点を ss を含む側と tt を含む側に分けたものを ss–tt カットと呼ぶ。カット容量は、元のグラフで ss 側から tt 側へ向かう辺の容量の和である。この例では ss 側を {s,p,q,a}\{s,p,q,a\}、tt 側を {b,t}\{b,t\} にすれば、横切る辺は a→ta\to t だけで、容量は1になる。

どの流れもこの境界を越える必要があり、総流量は1以下である。一仕事なら実際に割り当てられるので、最大流量も最小カット容量も1と分かる。元の三本の許可辺がある例では二仕事を割り当てられ、ss から出る二辺を切れば容量2になる。カットはこのように、通せる量の上界、ひいては割当不能の理由を示す。一般の最大流と最小カットの一致や、選択問題をカットへ帰着する手順は下位単元で扱う。

ここから先は、求めるものに応じて模型を読む。

  • 「全仕事を割り当てられるか」「最大で何仕事を任せられるか」なら、マッチングや最大流を使う。受け手が複数の仕事を担当できるなら、受け手から tt への容量を担当上限へ変える。
  • 「許可されたすべての組について、少なくとも片方の端点を選ぶには何頂点必要か」なら、最小頂点被覆である。両仕事の候補が aa だけの例では、頂点 aa 一つで全許可辺を覆える。二部グラフでのマッチング数との一致と復元は二部matching・Hall・Kőnigで学ぶ。
  • 「同じ仕事数を割り当てる中で、費用を最小にしたい」なら、許可辺に一回の割当の費用を別に持たせる。例えば元の例で p→bp\to b だけ費用2、他は0なら、一仕事の最小費用は0、二仕事では2となる。容量は使用回数、費用は選択の評価値であり、最小費用流・circulationで流量ごとの最適値を扱う。

成立条件と計算量

この割当模型では、左右の役割が分かれ、選択の可否を許可辺で、使用回数を容量で表せることが前提になる。禁止された組には辺を張らない。容量を大きくすると使用回数の制約が緩むため、禁止条件の代わりに使うことはできない。また、容量1は「高々一回」である。全仕事の割当は総流量が仕事数に達したことから保証した。

「特定の頂点だけは必ず使う」という条件は別に表す必要がある。ABC285 Gの問題文と公式解説では、二マスタイルをマッチングの辺とし、2 のマスを必ず選んだ辺の端点に含める。辺数だけを最大化しても、指定頂点をすべて使った保証にはならない。この違いは下限制約付きflowの実現可能性へつながる。

費用付き割当の接続先はABC247 Gの問題文と公式解説である。大学と得意分野を左右の頂点、人を辺とすれば、同じ大学・同じ得意分野の重複を容量1で防げる。選ぶ人数を流量に、強さの合計の最大化を費用の最適化に対応させる。上の二仕事の例は、この二部割当の仕組みを説明するための独自例である。

計算量は元の入力サイズだけでなく、構築後の頂点数と辺数を数えて評価する。最初の例は s,t,p,q,a,bs,t,p,q,a,b の6頂点、元の辺は 2+3+2=72+3+2=7 本である。残余グラフでは元辺ごとに逆辺も持つので、記憶する辺の枠は14本となる。

一般に仕事が nn 個、受け手が mm 人、許可された組が kk 個なら、頂点数は V=n+m+2V=n+m+2、元の辺数は E=n+k+mE=n+k+m。許可された組の一覧からの構築と、最終流量を見て割当を復元する処理には、それぞれ高々 O(V+E)O(V+E) 時間がかかる。

例えば、残余グラフを毎回幅優先探索して一つの増加路を見つける方法なら、一回の探索は O(V+E)O(V+E) 時間。この模型では各増加で流量が1増えるため、最大流量を FF とすると、最後の到達不能の確認も含む全体は O((F+1)(V+E))O((F+1)(V+E)) 時間、空間は残余辺・探索用配列・復元した割当を合わせて O(V+E)O(V+E) となる。ここで F≤min⁡(n,m)F\leq\min(n,m) であり、仕事0個なら流量0で全仕事を割り当てたことになる。候補のない仕事があれば、その仕事を通せず全仕事数には届かない。

この評価を、容量を大きくした一般のフローや費用付きの算法へそのまま使わない。より速い二部マッチング法、一般の最大流、最小費用流では、それぞれの下位単元の上界へ構築後の V,EV,E と必要流量を代入し、構築・復元を含めて制約に収まることを確かめる。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 青色(1600–1999)。割当て・容量・cutの制約を読み、matchingとflowへの還元を選ぶ入口。

対象色の読み方は本書の読み方を参照してください。

概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-flow-matching

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • Eulerウォークの次数・偶奇条件。

根拠