■学生論文賞受賞論文

グラフの向き付けに関する最適化問題の解法
小林 佑輔（東京大学工学部計数工学科 現所属・同大学院情報理工学系研究科数理情報学専攻）
指導教員 岩田 覚助教授

有向グラフが得られる向き付けのうち管用が最小とな

1． はじめにるものを求めよ．

2々辺連結な無向グラフが与えられたときに，々枝これを最小費用々枝連結向き付け問題という．最連結となるような最小費用の向き付けを求める問題は，小費用々枝連結向き付け問題は，最小費用有向カッ

最小費用々枝連結向き付け問題と呼ばれ，これは劣ト被覆問題なども含んだ広い枠組みである劣モジュラモジュラ流問題として定式化される問題である．この流問題として捉えることにより，多項式時間解法が得間題に対しFrank［2］は劣モジュラ流問題としての定られている．しかし，実際に効率的なアルゴリズムを式化を用いて計算時間0（々2タZ3〝7）のアルゴリズムを構構成する際には，各問題に特有の性質をうまく使うこ成している．ただし，頂点数を乃，辺の数を∽とすとが重要となる．

る．また，Gabow［3］はFrankのアルゴリズムに複最小費用k枝連結向き付け問題に対して，Frank雑なデータ構造を導入することにより，0（カ〝2〝プ）のはこの問題が劣モジュラ流問題に帰着されることを用計算時間によるアルゴリズムを実現している．本研究

いて計算時間0（々2プ73〝Z）の解法を構成している．また，

では，複雑なデータ構造を用いることなく0（が乃3GabowはFrankのアルゴリズムを基本とし，セント＋々乃2〝7）の計算時間で最小費用々枝連結向き付け問ロイド木（centroidtree）と呼ばれる複雑なデータ構題を解くアルゴリズムを示した．また，この応用とし造を導入することにより，0（々乃2∽）の計算時間によて有向カット被覆を0（乃2〝Z）の計算時間で見出すアルるアルゴリズムを実現している．本研究では，Frankゴリズムを示した．のアルゴリズムを基本とし，複雑なデータ構造を用い2．最小費用良枝連結向き付け問題
無向グラフ百＝（Ⅴ，E）は，任意の点集合ズ≠￠，Vることなく0（々3タ‡3十々乃2〝Z）の計算時間で最小費用々枝連結向き付け問題を解くアルゴリズムを開発した．
これは，k2n＝0（m）となるときにはGabowのアルに対して∂（ガ）≧々となるとき，々辺連結であるといゴリズムと同じ計算時間であり，しかもより単純なアう．また，有向グラフG＝（V，A）が々枝連結であるルゴリズムとなっている．これらのアルゴリズムの比とは，任意の頂点集合X≠れⅤに対して∂＋（方）≧々較を表1に示す．なお，表中の〟（乃）は乃行乃列のとなることである．ここで∂（X）はズとⅤ＼又とを行列同士の積の計算にかかる時間を表す．

結ぶ辺の数を表し，∂＋（X）はXから出てⅤ＼ズに入Frankのアルゴリズムは，始めにk枝連結な向きる枝の数を表す．すると，以下の定理が成立すること付けを求め，そこから，新たな々枝連結な向き付けが知られている．

への更新を繰り返していくものである．ある々枝連定理1（Nash−Williams［4］）．無向グラフE＝（V，結な向き付けが与えられているとき，ガ⊆Ⅴが臨界且）が2々辺連結であるとき，かつそのときに限り，集合であるとは，∂＋（ズ）＝々であることを表す．〃を各辺に適当な向きを付けることにより，々杖連結であるような有向グラフG＝（Ⅴ，A）を得ることができる．

表1最小費用々杖連結向き付け問題の解法の比較

定理1に関連して以下の最適化問題が自然に考えられる．

問題．2々辺連結な無向グラフに対し，各辺e＝〟〃の時間計算量
R弧k【2】

0（た2乃3m）0（れ2）Gabow【3】0（たm2m）

0（m）

0（たれ〟（m））0（m2）

両方の向きにそれぞれ向き付けの費用c（〟〃），C（〃〟）が与えられている．このとき，々枝連結であるような
2005年12月号

領域計算量本論文 0（た3m3＋たm2m）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

0（m2）（49）839

含むすべての臨界集合の積集合を斤（〃）とすると，最表2 最小費用有向カット被覆問題の解法の比較

小費用ゑ枝連結向き付け問題を解くアルゴリズムの時間計算量

更新手続きの中では，すべての頂点〝，〃∈Ⅴに対して〟∈β（〃）であるか否かを判定することが必要とな

R弧k【110（れ3m）0（れ2）Gabow【3】0（れ2m）

0（m）

0（れ〟（m））0（m2）

0（れ2m）

0（mm）

0（れ2m）

0（几2）

る．Gabowは，複雑なデータ構造を用いてすべての臨界集合を表現することにより，〟∈β（〃）であるか領域計算量

Shepherd−Vetta［51

否かを判定したが，本研究では，α∈斤（ぴ）であるか

本論文否かの判定に，必ずしもすべての臨界集合が必要なわけではないことに注目して，複雑なデータ構造を必要を導入することにより，0（裾2∽）の計算量を実現してとせずに，α∈斤（〃）であるか否かを以下のように判いる．それに対しShepherd−Vettaは，劣モジュラ流定した．

問題の持つ性質に加えてこの間題特有の性質をうまくある固定した頂点γを含まず，〃を含む臨界集合用いることにより，複雑なデータ構造を用いる必要の全体を予言とし，γを含み，〟を含まない臨界集合全ない主アルゴリズムでGabowのアルゴリズムと同じ体を矛云とおく．すると，才芸，ア云は和集合と積集合計算時間を持つものを構成した．しかし，Shepherd−に関して閉じている．よって，矛去の中で最小の集合

Vettaのアルゴリズムは前処理を多く施すために，グが存在するのでこれをβJで表す．ただし，才芸＝￠ラフを乃個分保持する必要があり，領域計算量がのときにはβJ＝Ⅴとする．また，予言の中で最大の0（乃研）となっている．本研究のアルゴリズムは，複集合が存在するのでこれを斤諒で表す．ただし，矛；雑なデータ構造を用いることのない計算時間0（〝2研）＝￠のときには斤左＝￠とする．すると〟∈β（〃）であのアルゴリズムで，しかも領域計算量が0（乃2）となっることは，〟∈βJかつ明日㍍であることと同値であている．このアルゴリズムを実装したところ，CPUる．そこで，すべての頂点についてβJと斤古を求めがIntelのPentium41．60GHz，メモリが1GBであることにより〟∈β（〃）であるか否かを判定することる計算機で，乃＝50，研＝100の問題を1秒以内で，ができる．

乃＝200，研＝400の問題を1分程度で解くことができた．また，乃，偶の値を変化させて，計算時間がおよ

3．有向カット被覆への応用

そ乃2ク形に比例することを確認した．

弱連結な有向グラフが与えられたときに，いくつか参考文献の枝を縮約して強連結なグラフを作ることを考える．
ただし，有向グラフが弱連結であるとは，枝の向きを無視した無向グラフが連結であることをいう．各枝を縮約する費用が与えられているときに，強連結なグラフを得る最小費用の縮約を求める問題を最小費用有向カット被覆問題という．本研究では，最小費用有向カット被覆問題が最小費用々枝連結向き付け問題の々＝1の場合に帰着されることを用いた，0（乃2肌）の計算時間による単純な解法を示した．
最小費用有向カット被覆問題に対しては表2のような計算時間で解くアルゴリズムが知られている．
Frankのアルゴリズムは劣モジュラ流問題の最適［1］A．Frank：How to make a digraph strongly con−nected．CombinatoYica，1（1981），pp．145−153．

［2］A．Frank：Analgorithmforsubmodularfunctions
ongraphs．Annals〆Dtsc柁teMathematics，16（1982），
pp．97−120．

［3］H．N．Gabow：Centroids，repreSentations，andsub−
modular貝ows．JAなorithms，18（1995），pp．586−628．
［4］C．St．）．A．NashLWilliams：On orientations，COn−nectivity and oddLVerteX−pairingsinfinite graphs．
（加挽ぬ町人必摘酬矧触，12（1960），pp．555−567．

［5］F．B．Shepherd，A．Vetta：Visualizing，finding andpacking dijoins．G74h 771eO7y and Combinatorhll

性条件に基づいた主双対アルゴリズムであり，

qtimization，D．Avis，ed．，SpringerVerlag，2005，pp

GabowはFrankのアルゴリズムに，最小費用k枝連219−254．

結向き付け問題に用いたものと同じ複雑なデータ構造

オペレーションズ・リサーチ

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