| 学籍番号 | 90438032 | 所属研究室 | 藤重研 |
| 氏名 | 辻 本 昭 一 | ||
| タイトル | 最小費用フローに基づくグラフ描画アルゴリズム | ||
|
1. 序論 近年，グラフィックベースの計算機インターフェイスの発達に伴い，与えられたグラフを画面上に適切に自動描画するアルゴリズムの研究が進んでいる． グラフ描画の一つの適切な基準の数理モデルとして，最小ベンド数平面格子直交描画問題がTamassia [2]により提案されている．この描画問題は最小費用フロー問題に帰着できるという興味深い性質がある．本研究では，最小ベンド数平面格子直交描画の仕組み及びこの問題において最高の理論的性能を持つ，Garg--Tamassia [1]の最小費用フローアルゴリズムについてまとめ，またプログラムを作成し描画を実行した． 2. 最小ベンド数平面格子直交描画問題} 点集合V,枝集合Eからなる無向グラフG=(V,E) を入力とし，最小ベンド数平面格子直交描画を出力とする問題を考える． グラフGの辺が互いに交差しないように平面に描画したものをGの平面描画といい，平面に埋め込み可能なグラフを平面グラフという．平面グラフGの各点を点として2次元整数格子の格子点に配置し，各辺を点を結ぶ直線として平面描画したものを，平面グラフGの平面格子直線描画という．さらに，各辺を水平成分と垂直成分の列として平面描画したものを平面格子直交描画という．つまり入力された無向グラフに対する最小ベンド数の平面格子直交描画を求めるのが最小ベンド数平面格子直交描画問題の目的である． 最小ベンド数平面格子直交描画問題はまず最初に，与えられた無向グラフを最小費用フロー問題に変換する．そして最小費用フロー問題を解き，その解で描画を行うことで解決できる．またこのとき最小ベンド数は最小費用と一致する． 3. AugBlockアルゴリズム Garg-Tamassiaの最小費用フローアルゴリズムAugBlockを説明する．AugBlockはネットワークN=(G=(V,A),c,r,s,t)に対する最小費用最大フローを求める．ただし，G=(V,A)は点集合Vと有向枝Aにより定義されるグラフであり，c,rはそれぞれ容量関数c:A\rightarrow R及びコスト関数r:A\rightarrow Rである．そしてs,tはそれぞれ集合Vに含まれる点でそれぞれ始点と終点を表している．AugBlockアルゴリズムを示す． AugBlockアルゴリズム [Input:] ネットワークN=(V,A,c,r,s,t). [Output:] N中の最大フロー値に対する最小費用フロー. [Step 1:] A_1を零フローに対するNの許容ネットワーク(流せ得る状態を表す補助ネットワーク中の同一コストを持つs-t有向道の集合を許容ネットワークとする); \leftarrow 1; F_1は零フロー; [Step 2:] A_iに非零な最大フローが存在すればStep(3)へ，なければ終了. [Step 3:] 第iステージA_iに対する最大フローf_iを見つけるのにAugPathBlockFlowアルゴリズムを同時に動かし先に出たフローをf_i;F_{i+1} = F_i + f_i; A_{i+1}をフローF_{i+1}に対するNの許容ネットワーク;i: = i + 1;Step(2)へ; またここで出てきたAugPathとBlockFlowは共に与えられたネットワークに対する最大フローを求めるアルゴリズムである．与えられるネットワークは共に許容ネットワークである． AugPathはネットワーク中の増加有向道をなくすまでフローを流して行く．$s$-$t$道が無くなったときまでに流したフローがそのステージでの最大フローである． BlockFlowはネットワークをs-t間の距離で更に分ける．最小距離のs-t道集合にフローを流しs-t有向道がなくなれば(つまり全有向道対し1本でも飽和する枝があればよくて，このフローをブロックフローという)，次の最小距離の有向道集合に対して同じことをする．有向道がなくなるまで繰り返した総フローがそのステージでの最大フローである． このアルゴリズムはネットワークの点数をn,枝数をm,フローの最小コストを\chiとするとO(\chi^{3/4}m\sqrt{\log n})で実行可能である．描画問題では枝数m及び最小ベンド数がO(n)であることが知られており，O(n^{7/4}\sqrt{\log n})時間で描画可能なことが示される． 4. 実験と結果 AugBlockのStep3でAugPathのみを使用するプログラムを実装して描画を行った．点の数と枝数の異るグラフを入力させてそのアルゴリズムの実行時間を測定し，計算時間が枝数によらずO(n^2)となることを確認した． 参考文献 [1] A.Garg and R. Tamassia: A New Minimum Cost Flow Algorithm with Application to Graph Drawing. it Proc. Graph Drawing'96, LNCS, 1190, 1997 pp. 201-226 [2] R.Tamassia: On Embedding a graph in the grid with the minimum number of bends,it SIAM J. Comput, 16(3),1987 421-444 J81-A(1998),863-869. |
|||