l川刷‖‖………l川…l……l州………lll州‖‖‖＝‖‖‖‖‖‖‖‖‖＝‖‖‖＝‖‖‖＝‖‖‖‖‖‖‖‖＝‖＝＝‖‖＝‖‖‖‖‖‖＝‖‖＝＝‖m‖＝‖＝‖‖‖＝＝‖‖‖＝＝‖‖‖＝‖＝‖‖‖‖‖‖＝‖‖‖＝‖‖‖‖‖‖＝‖‖‖‖‖＝‖＝＝‖‖‖‖‖＝‖‖‖‖＝‖‖＝‖川…

l・ − ・・・√∵キ．：
浅野 孝未……ll…………＝‖‖‖＝‖‖＝州…ll………l‖‖‖‖‖州…ll…‖‖州…‖‖‖＝州Il…l……州…………………………ll……ll…………l…………ll…………ll…………l…ll…………l……lll……ll…………………………………ll…ll………

、

1・、て勝敗を必ず決めるので、引き分けは起きないものとしてよい。また、最終的に勝数が最大のチームが複数数理計画の様々な問題がグラフ。ネットワーmクを用

チれ・ム存在したときには、プレ鵬オフで優勝チ山ムをいて定式化され解かれている。グラフゎネットワー叫ク決定するので、プレhオフに出場できれば、優勝するを用いる利点は、問題が明確になって目で見て直観的可能性はある。に解を求めることがある程度できること、および情報

上記の問題は、貴大フロー最小カット定理に基づい科学の分野で展開されたアルゴリズムやデーⅦ夕構造て解決できる。もちろん別の方法でも解けるが、ネッを用いて大きいサイズの問題も効率的に解ける点な

トワ・−【タブロー一に基づく方法が最も自然であるのでどであろう。たとえば、次のような問題などもグラフ。

後述サる。また次の間題もネットワーク間題として解ネットワL・叫夕を用いて定式化され解ける。

左ナる。ここで、訂乱，…ヲ訂6は教師でC19。。8，C6は科目

以下の蒙はある年のCリーグのペナントレースのであり、表の数字は各教師のそれぞれの科目の得意度＄月某日終了時点の成績および残り試合の対戦数で（10点滴点）を表している。各教師に科目を重複なくユある。この時点で最終的に中日の優勝する可能性があ科目担当してもらい、総得意度（担当科目の得意度のるかどうかを判定せよ。可能性があるときはその可能総和）を最大にするのがこの間題である。これは最適性を実現するような9各チ如ムと他のチ、−・−−ムとの残り割り当て問題と呼ばれるネットワーク間題の有名な問試合の対戦成績の例を記せ。

題の例である。

チーム

勝数

負数 残り試合梁ヤクルト

663862横浜

し篭52 E垂転コ＝至26と÷1弓56

巨Å

2647275且2〆766286334に璽更ヨ＝垂＝

残り対戦数タルト要広島巨人横浜阪神中日ヤクルト65 28芸ノ監島H67 4 5 7 36横浜．錠3阪神

望5

念 【墓⊆一童野．、

グラフ〔ネットワーク最適化の研究は日本でも極めて活発に実行されてきた。伊理正夫先生や冨澤信明先生による貴大フローMアルゴリズムや最小費用フローアルゴリズムはFordⅦ凱11kersonやEdmondsoⅨarpのアルゴリズムとほぼ同時に発▲表され、この分・野の研究の6 66 声799な裳㍉環＝り帥−グのルhルでは、引き分けは再試合をし端緒となっている。また藤重悟先生の強多項式最小費用フロ山アルゴリズムも最初の甘ardosの埠多項式アルゴリズムとともに有名である。また最近では、最小カットを求める茨木俊秀先生9永持仁先生の研究は極あさの たかお 中央大学理工学部情報工学科

めて斬新なアイデアに基づいていて、画期的な研究と、 、 −・′・ト ．・ −して全世界的に注目されている。また、福田公明先生の逆探索法や平面グラフに対する西閑隆夫先生の著

圏爵（22）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレー帽ションズqリサーチ

書も世界的な注目を浴びている。これらの成果は、藤をβ，fカットという。β，モカツト且（X，Ⅴ一方）の容量を重悟先生・室田一雄先生編の「離散構造とアルゴリズ

叩（∬）で表す（叩（ズ）＝∑。∈榊，Ⅴ−ズ）叩（e））0する

ム、Ⅰ，ⅠⅠ，ⅠⅠⅠ，ⅠⅤ」（近代科学社）で詳説されている0拙著「情報の構造、上下」（日本評論社）でもいくつか扱っと任意のフローJと任意の∂，書かット且（ズ，Ⅴ一方）に対して、ている。このように、グラフ・ネットワーク最適化の射αg（J）≦c叩（X）

研究に日本が重要な貢献をしているが、研究は広範にわたるので、ここでは最大フローアルゴリズムを主にが成立する。流量最大のフローJと容量最小のβ，舌カッ最近の研究動向まで含めて解説したい。さらに興味のトを選ぶとこの不等式は等式で成立する。これが有名ある読者は是非上記の文献および後述の参考文献等な最大フロー・最小カット定理である。

を参照されたい。

定理1．ネットワークⅣ＝（Gr＝（Ⅴ勒c叩，β，りに2．最大フローアルゴリズム

おいて、最大のフローの流量と最小のβ，fカット容量は等しい。

2．1 フローとカット有向グラフG＝（Ⅴβ）の各辺e＝（γ，Ⅷ）∈捌こ正の実数の容量c叩（e）が割り振られているネットワーク

2．2 For（トFulkersonのアルゴリズム
最大フローを求めるFord一軒劇keTSOnのアルゴリズ

Ⅳ＝（G＝（町恥c叩，β，f）において、入口β∈Ⅴからムは、ゼロフローから出発してフロー′を更新してい出口f∈Ⅴへの流量最大のフローを求める問題が最くが、その際フロー′の残余容量ネットワークⅣ（J）

大フロー問題である。なお、Ⅳのフロー′は、辺集合を用いて、入口βから出口fへのバスク＝P（β，f）を厨から非負実数集合月＋への関数で以下の2つの条件求め、そのパスPに沿ってできるだけフローを流してをみたすものとして定義される。

．fを増加し更新して、最終的にⅣ（′）にβから才へのパ（A）任意の辺e∈割こ対して、0≦封e）≦c叩（e）・スがなくなるまで繰り返す、というものである。フロ（B）β，舌を除く任意の頂点領∈Ⅴに対して、ーJに関する残余容量ネットワ・−クⅣ（力は以下のようなものである。各辺e ＝（γ，W）∈ 捌こ対して、∑J㈲＝e＝（叫び）∈∂￣（り）∑ J伺・〃e）＜c叩（e）な・らばさらにc叩′（e）＝C叩（e）∵頼）

e＝（uル）∈∂＋（む）だけ流せるのでそれがe＝（γ，ひ）の残余容量であり、ここで∂￣（γ）（∂＋（γ））はγを終点（始点）とするⅣの辺の封e）＞0ならば〃e）だけ減らせるので逆向きの仮想集合を表す。（A）は各辺を流れるフローの億が容量以的な辺e兄 ＝（町γ）を考え、その辺e月 ＝（ひ，γ）に下であることを示している。（B）は入口・出口を除い沿って封e）だけ流せるので辺e属 ＝（叫γ）の残余容て、流量の保存則（流入量＝流出量）が成立している

量はcα即（e虎）＝封e）となる。従って、仮想的な辺ことを示している。従って、（B）は、の全体をが ＝ 〈e月 t e ∈ 且）とすると、フロー∬＝ ∑ 拍）−
e＝（β，∽）∈∂＋（β）∫に関する残余容量ネットワークⅣ（J）＝（G（J）＝∑ニ ノ㈲e＝（叫β）∈∂￣（β）とおけば、（Ⅴ且（J）），Cα捏，β，りは且げ）＝（e∈且け（e）＜c叩（e））∪（e属∈がけ（e）＞0），∬＝ ∑ 拍）【 ∑ 拍）
e＝（叫t）∈∂【（f）e＝（土，叫∈∂＋（t）が成立することを意味している。すなわち、βから流Cα即（e）＝ C叩（e）−．f（e）（′（e）＜cαp（e）），
c叩J（e月）＝ 〃e）（J咋）＞0）

出するフローの正味量∬はfに流入するフローの正味量に等しい。この∬をフローJの流量といい、γαg（J）と書く。β∈ズ，f∈Ⅴ一方となる点の部分集合ズに対として定義できる。

フロー〃こ関する残余容量ネットワークⅣ（J）におけるβからfへのバスク（β，りは増加パスと呼ばれしてる0実際、P（β，f）上の辺の残余容量の最小値を△（P）
β（ズ，Ⅴ一方）＝†（γ，ぴ）∈β巨∈耳ル∈Ⅴ一方）
1998年2 月号とし、各辺e∈且を流れるフローー′を© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（23）89プ（e）＋△（厨）（e∈厨（β，雷））頼ト△（P）（e腐∈脛（β9￡））♂′（e）：＝・・・・−、、． l・鷺恥ヂ）の極大フローヂ′′が0（m花）（乃＝附m＝圃）の手間で求められること、および反復ごとにβから舌へのパスの長さが1以上増加することより反復回数がの（陀）であることがいえて、Dimicの最大フローアルと更新すれば、♂′もⅣのフロ山となり、かつゴリズムの計算時閤は￠（m孤2）となる。

即離（。ダ′）＝即叫。ダ）＋△（厨）となるので流塵を増加できる（△（脛）＞りむこ注意されたい）。従って、㌦がⅣの最大フローならば、♂に関する増加パスは存在しない。進定理牒仏ネットワ・−叫クⅣ＝（G＝（町属），CαP，β9諺）の最大フロhは、Dimic法により0（m花2）の手間で求めることができる。

もいえる。

定理2Lヨネッ恥り・仙クⅣ＝（α＝（町町牒動項）におし−て、フローずが偉大フ田山であるための必要十分条件はぜに閑サる増加パスが存在しないことである。
Fo∬d叩訊且1ke町SOmのアルゴリズムより、各辺eの容量

・ −・：・・サニー∵ こ・・二∴．∴・次の衷はこれまでに提案された代表的な最大フロー叫アルゴリズムの性能一欄である剛。いずれも高速化のためヂ」夕構造にエ夫を凝らしているが、実用的cαp（e）が整数のときは、残余容蛍も常に整数となり、なレベルでの性能評価は今後の計算礫実験によって明従って、更新で得られるフローーダ（e）も整数となるのらかにされるものと思われる。

で、次の整数性定理が得られる。
定理3じ（整数性定理）ネットワhクⅣ＝（α＝発表年

著者1951》an七z五g

笹津坊州都勘りにおいて、各辺eの春慶cαp（e）が整数ならば、フ田山錘）も整数となるような最大フロープ
鼠970が存在する。

・

mim孟c2Ka∬ZamOV

・、、・

・− ∴

1974の容量が無理数であると反復が有限回で終了しなかっm柁（log陀）2

蜜 Slea′もor−Ta雨amm陀log陀1986 Goldberg−Taわ乱n mァtlog（m2／m）
ユ99（〕 Che扇yameもal。

閃3／胤og閃

ゴリズムは多項式オhダのアルゴリズムではない。こヨユ90 Alom ユ92 K孟mgeも融． m閃＋和叫ビ 193 Ph五1ipseもa且． m陀（logm′礼乃＋log2中和） 194 Ⅸimge七弧 m陀logm佃log几）陀れに対して、Edmom組s剛Ⅸarpは辺数量小の増加パスを上の衷は、最初の望つを除いて強多項式オーダのアたり、誤った備に収束したりする。また辺の容量がすべて整数であるとしても反復回数が辺の容量に比例するときもある。その意味で、鮮0訂d−『ulkersonのアル開閥2押−り2

巨膵開

い980

凱肌H軋施e訂SOmのアルゴリズムには欠点があり、辺∬3m陀＋陀8／3鼠og陀選ぶことでこれらの欠点を解消した。Dimic（デイニッルゴリズムである。実際上生じる問題では、容量は整ツ）はこの考えをさらに進めて、残余容量ネットワー数に近似されて∴整数の容量をもつネットワークとしクⅣ（♂）を幅優先探索して、各頂点γの入口βからの距て扱われることが多い。そ・のような場合は、容量の最離（辺数最月、のパスに含まれる辺数）geγe嘲を求めて大値をぴ【とおいてⅣを表現するためのビット数且ogぴを用いて計算の手間を見積もるのが自然である。こ厘且（♂）ニ‡（即，榔）∈腰（ダ）頼購亜司二臨属国＋り′．●・、・・．′∴ ′＼・・・● 、・一 ●・′ ・−：・・・∴ 〜を構成しレベルネットワーク丼乙（♂）上での極大フローのような観点からの蔵大フローアルゴリズムも多数提案されている。強多項式オーダのアルゴリズムと性能を比較するため、通常鼠og打＝＝の（iog穐）の相似仮定（sim温ia∬温七yassⅧm画on）が用いられている。さらに、㌔′メを求め、この相似仮定のもとでlog穐の多項式で表現される部♂（α）♯厨′′（α）（α∈厨エ（プ））分は無視して得られる性能（の限界）を球場限界（ball−ず（α巨ダ′′（α屈）（α虎∈屈且（ず））parkboumd）という。たとえば、0（m孤logⅣ）などは、一院ヨ闘琶亭肖Bと更新しながら、Ⅳ（♂）にβから若へのパスがなくなるまで繰り返して、最終的にⅣの最大フロ巨¶を求める方法を提案した。
盟田（24）

球場限界はm花となる（の＊（m犯）と表示）。
，，■・・一般に、のimic法などの土許加パスを求めてフローを増加していく方法は、フ隠hを様々な流量をもつパオペレ・−一一ションズDリサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

ーの流量50となり、C叩（β）＝51となり、中日が優勝するとすると残り試合1試合消化できなくなってしまう。従ってこの時点で中日の優勝の可能性は完全に消滅している。次の例で阪神の優勝する可能性はどうだ
ろうか。

図1．中日の優勝可能性判定のためのネットワークスの和として表現しているとみなせる。従って、フローのパス分解に基づく方法といえるが、パスの総数はn（m乃）になるため、パス分解法に基づくアルゴリ

チーム

勝数

負数 残り試合数

ヤクルト

663826広島

584032巨人

564727横浜

504733

阪神366331

中日336433ズムでは最悪の場合n（m几）の手間はどうしてもかか
残り対戦数 クルト 広島 巨人 横浜 阪神 中日

ることになる。これが、パス分解法の障壁といわれヤクルト

るものであるが、これを克服しているのはCberiyan

6∂

57 10 5広島

6巨人

57年のFOCS（IEEE Symposium on Foundations of横浜

510 3

Computer Sciences）の会議で、相似仮定の下ではあるが、パス分解法の障壁0（m托）を大幅にクリアする

阪神

2569中日8466etal．のアルゴリズムだけである。しかしそれも、密ネットワークに限定されている。これに対して、19970＊（minim3／2，m几2／3））の最大フローアルゴリズムが提案されている。それについては4節で紹介する。

2。5 優勝可能性判定問題への応用
図1は第1節で紹介した中日の優勝可能性を判定す

8234669699前と同様にネットワークを作り最大フローを求めると今度は最大フローの流量60となり、C叩（β）＝60となり、阪神が優勝する可能性があると判断できる。そのときの対戦成績の例は以下の通りである（各行がそのチームの対戟勝ち数である）。

るためのネットワークである。上から2段目の点は左から、ヤクルト対広島、ヤクルト対巨人、ヤクルト対横浜、ヤクルト対阪神、広島対巨人、広島対横浜、広島対阪神、巨人対横浜、巨人対阪神、横浜対阪神に対応する。入口βからそれらの点に向かう辺の容量は残り対戦数になっている。一方、上から3段目の点は左クルト 広島 巨人 横浜 阪神 中日ヤクルト広島

5巨人

530000400030002横浜510 0から、ヤクルト、広島、巨人、横浜、阪神に対応する。

阪神

2569

中日が残り試合全勝しても67勝にしかならないので、中日

846490

他のどれかのチームが68勝以上してしまうと中日は優勝できない。そこで上から3段目の点から出口fに

上記の問題では、一般にⅣチーム存在するとき、向かう辺の容量は、対応するチームが67勝になるま

ネットワークの頂点数陀、辺数mはともに0（Ⅳ2）となでの勝ち数となっている。他の残りの辺の容量は∞とり、Dinicの方法で解くと手間は0（m乃2）＝0（Ⅳ6）とみなしてよい。このネットワークで最大フローJを求なりそうだが、第3段目の点数が0（Ⅳ）であるのでβめその値即αg（J）が、β，才力ツトβ（β，Ⅴ−β）の容量c叩（β）

からfへのパスの長さは最大で0（Ⅳ）であり、したがっに等しいときは、すべての残り試合を消化することがて、反復回数も0（Ⅳ）となり、全体の手間は0（Ⅳ5）でできて、中日が優勝するためのシナリオがフローJである。より厳密に解析すれば、おそらくさらによい手表現されている。残念ながら、この例では、最大フロ間が得られるであろう。

1998年2 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（25）91

且 C245≠

4、こ．・・キ．．‥・‥●∴肯・・・− −、 ￣−・′・、−こ ●−ご．・・

r3 C4 C5 C635242

相似仮定の下でパス分解法の障壁0（門γ托）を大幅に465クリアするぴ（mim（m3／2，m乃2／3‡）の最大フローアルゴリズムについて紹介する。これは1997年の『OCSTl 毯 田 】 田 2 唾 田 3 田 四 班4 岱 5 5 魂 7 6 当【リ 5 7 8 4 6 7 Fi壷jき 田 2 ⊇ 田 4 2の会議で鎧0且dbe咽偲aoによって提案されたものであ引航まず∴いくつかの記法を導入する。便宜上、辺eニ（壱ッカ■）に対して逆向きの辺e劇ニ（ブラ豆）が存在しないときは、仮想的にe戯を考えその容畳を0と考え、常に逆向きの辺があるものとする。もちろん逆向きの辺㌔が元から存在するときは容量はそのままであ、● ヰ・・三草ニシミ・ニ≒・∴・‥−：−‥十ごミ‥ミる。そして、。ブロー叫。ヂは頼）＝のあるいはプ（e虎）＝0

第1節で述べた得意魔の表で、コスト＝ 乱0一得意度として書き換えると上の表が得られる。ここで各行盲を左端点嘉に対応させ、各列jを右端点Jに対応させて完全2部グラフ勒6を考え、左端点盲から右端点も斎に向かう有向辺の慧ス恥を止の衆の嘉J要素を割り当てる。そしてÅmβから各左端点へ向かう辺と各右端点から出口詰へ向かう辺を加え、それらの辺のコストをのとする。すべての辺の容量を乱とし、．βから詰への流塵㈲の費用磯舟のフm鵬を求める。流量乱なら話は単純で単にぶから藍への（辺のコストを長さと見なして）最短パスを求める聞題になる。このフロ1トmずに対して残余春慶ネッ隕Yブし叫タⅣ（封を作り、逆向きの辺e厨（に沿ってプ田−を流すと費やしたコストが戻ってくるの、で）のコース匹をb叫CO呵e）と定め、またβから君へのいずれかをつねにみたすものとする。したがって、各辺の残余春慶は伽鞘（e）ニC叩（eト錘）＋封e虎）、叩鋸（e児）ニC叩（e柁ト【〟□㌔（e兇ト…（e）となる。残余春慶ネットワ、州クⅣげ）は残余春慶が正の辺のみからなる。都翫に町．の長さを割り振る関数ゼが与えられたとき、各点嘉のラベルd（嘉）を用いて各辺（五，戊）の簡約コスト／どd（机車封串正目戎（ゴトd（去）を定義し、つねに簡約コストが非負であるようにする。d（若）＝0として、すべての辺の簡約コストを非負にできるとき、点五のラベル坤）を距離ラベルと呼ぷ。長さ関数ゼに対する各点言の距離動（嘉）を哀から詰までの最短距離として定義する。すると動は距瀾汚ベルとなり、任意の距離ラベルdに対してば≦動イすべての点威で戊（威）≦ばβ（嘉））が、●一叢大プロト¶の流量と現在の流堂の差の上界をダをの最短パスを求麿㌔フⅧ−♂を更新する。こうして、各流塞に鮒も／て費用蔵刃、のフ田−が得られる。これは伊理によって提案された方法であるが、辺の長さが負のものが存在するので、最短パスを求める通常の恥瀬軸撒接が適用できない。富澤は、距離関数という暴力、費用フロ山間題の双対問題の変数に対応する変数を導Åしで、負の長さの辺をなくし通常のDijk山地撒法ができるようにした。この手法を用いて上記の割り当て関題を解くと、完全2部グラフの辺eで、プ用いて評価する。辺の容量の最大値をぴとおけば最・l・・ヽ ●−一 一● − ・・■・●ゝ ′㌫の且dbe‡hg…R乱0のアルゴリズムではこの∬を各フェーズで半分になるまで更新を繰り返す。ダ ＜1となれば、最大 ブPロー鴫が求まったことになるのでフェ山ズの回数は高々ユ＋且喝（γとぴ）である。各フェーズの最初のダに応じてAを息ニ「mim（mり2っ陀2／3‡田か叫頼）ここ 乱の辺の集合財は最適割り当て問題の解になる。上の例では、。〜ぼ ニ‡（鮮且ヲC￠），（班2ラC2），として定義し、流量△のフローーー。ヂ′あるいは（そのよう（粁39C5）ヲ（諾「4，C3）ヲ（訂5ぅぴ4），（y6ヲC刃）となりい除得意なフローがないときには）流量△未満の極大フロー。デ′・．三

科目数Ⅳのときは最短パス問題をDi錘s七訂a法での（Ⅳ）

を求めて、流畳プを増加し更新サる。各フェーズでは流量△の、プロhゾ′での更新は高々m血（mり2っれ2／3）臥極大ブロ十∴㌣での更新は高々6min‡mり2，循2／3）回し回解けば得られるので手間は岬3）である。−一般の最か起きないことがいえる（後述）。さらに流量△のフロ

パ、費用プロ両問題に射しても藤登らが強多項式オーーくヂ′あるいは流量△未満の極太フロー。ヂ′を求めることダのアルゴリズムを与えている。

はの（m且og（冊2／7職））の手間でできるので全体の手間は・、：．・ ．・、

最適割り当て問題は、この例のように、教師数Ⅳ、国選（26）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーーションズ。

リサ…チ0（mminiml／2，n2／3）log（n2／m）log（nU））となる。

詳しい証明は省くが、極大フローJ′による更新で実際に流量△のフローJ′あるいは流量△未満の極大はdどイβ）＞d （ぷ）が成立し、さらにdgは長さ閑散β′

フローJ′を求めるネットワークはこれまでの単なる残に関しても距離ラベルの条件（・叛（云，j）＝ゼ′（よ，j）十余容量ネットワークⅣ（J）とは少し異なる。残余容貴

毎（J）一心（去）≧0）を満たしている。さらに、残余容ネットワーク〃（．f）の各辺eに対して長さゼ（e）を以下

量ネットワークⅣ（J）の各辺eの残余容量c叩パe）を幅のように定義する。と見なして長さゼ（e）との横c叩バe）ゼ（e）をその辺の体（c叩パe）≧3△）

ゼ（e）＝

〈：

（cα即（e）＜3△）・

さらにgに基づいて点からfへの距離df（りを計算し、ホ（盲）＞dg（j）またはdf（去）＝dg（J）かつ埠，j）＝0を満たす辺（盲，メ）を使用可能辺といい、使用可能廼のみを使ってフローを増加更新していく。なお、使用可能辺は各点からfへの最短パスのいずれかに含まれる辺である。便宜上、使用可能辺の集合をA伏ゼ，d ）と表す0使用可能辺からなるグラフGA＝（VA（J，f，dg））

は正の長さの閉路をもたないことがいえる。さらに、棟と考え、全体積Ⅴ恒，ゼ＝∑。∈叩）叩J（e）g（e）を用いて、最大フローの流量と現在の流量の差の上界ダをダ≦Ⅴ叫，g極（β）と評価できる。呵J）においてβから￡への任意のパスに沿って流量1だけフローを増加す
ると巌だけ体積が減るからである（体積は定義より非負）。こうして各段階で辺の残余容量の貴大値を〟とおくと、Ⅴ叫， ≦m凡才、C呼（ぶ，訂）≦m〟／み（g）を満たす0さらに、叩（ぶ，r）≦（缶）2〟も示せて、この2つから極大フローJ′による更新は高々各フェーズで血n（6汀乙1／2，5れ2／3）回であることが示せる。

定理4．ネット ワークⅣの最大フローは、0（mmin（ml／2，几2／りlog（㌦／m）log（几打 の手間で求2△≦c呼パ豆，ブ）＜3△，d（査）＝咄），C叩J（j，去）≧3△を満たすような辺（よ，j）を特別な辺と見なして上記の長さ関数ゼを下記の長さ関数すに変更する。
（eは特別な辺）串）＝（冒g（e）（それ以外）．

もちろんこのように変えても、dg＝dぞは成立する。
使用可能辺からなるグラフGA＝（VA（．′，ろdg））の各強連結成分（長さ0の辺から形成されている）をそれぞれ1点に縮約して得られるグラフの各辺の容量をⅣ（J）の対応する辺の残余容量としてできるネットワークⅣA（J）上でざからfへの流量△のフローJ′あるいは極大フローJ′を求やる（0（mlog（㌦／m））の手間でできる）。こうして、フローを増加更新していく。もちろんフローを更新するときは、締約した点を元の点に戻して行う。これは各強連結成分の中から1点を代表点に選び、その点を根とする2種類の根付き木を用いて調整できる。更新されたフローJ′に対応する長さ関数 ′を用いてさらに上記のことを繰り返す。そして、夷（8）個の特殊なβ，モーカット（ぶた，孤）（鳥＝1，2，…，dg（β），
5 ∈ 動 ＝（u ∈ VId〆γ）≧ 見圭f ∈ 苅；＝V一範）のうち容皇最小のもの（且r）を求め（0（m）でできる）、容量c叩（β，r）＝（c叩（斎，j）l去∈β，J∈r）がc叩（β，r）≦ダ／2を満たすようになったときそのフェーズを終了し、新しいフェーズにダ：＝C叩（β，丁）とめることができる（打はⅣの辺の最大容量）。

5．ぁわりに他の最適化問題に対Lても重要な成果が発表されている。M．Thorupによる無向ネットワークの最短パスを0（m）の手間で求めるアルゴリズムおよびB・仇aze11eによる0（mα（m，可logα（m，乃））の手間で最小スパンニング木を求めるアルゴリズムがそれである（α（叫可はアツカーマン関数の逆閑散）。これらは、従来の壁を破る画期的な成果であるが、文科1】と同じプロシーアイングに載っている。またネットワ

ークアルゴリズムのプログラムや薬用化アルゴリズ
ムが載せてある東大の松井知己先生とA．Ⅴ．Goldbcrgのホームページを以下に紹介しておく。極めて有用であるのでご興味のある方は参考にしていただきたい。
http：／／www・misojirolt，u−tOkyo・aC・jp／tomomi／opt−

code．html
http＝／／www・neCi・nj■n軋COm／homepages／avg／index．html

参考文献【1lGoldbergA．Ⅴ．andRaoS．＝BeyondtheFlow−

Decompo5ition丑arrier叩，Proc・38thIEEESympo−

Sium Foundations of Computer Sceince，Miami
Beach，1997，pp．2−11．

して入るものとする。
1998年2月号（27）93© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.