| 学籍番号 | 90486011 | 所属研究室 | 藤重研 |
| 氏名 | 岡 澤 潤 | ||
| タイトル | ２部グラフに対する効率的な辺彩色アルゴリズム | ||
|
1. 序論 辺彩色とは，グラフの辺に対する色の割り当てのことであり，同一の点に接続する 辺が同じ色にならないという条件をみたすものである．与えられたグラフに対して 最小色数の彩色を求める問題は彩色問題と呼ばれる．本研究では，タイムテーブ ル作成等に適用されている２部グラフに対する辺彩色問題を考える．辺彩色問題は 古くから研究され，改良の道を歩んでいる．その中でも，Schrijver[1]の アルゴリズムに注目をする．Schrijverの２部グラフに対する辺彩色問題アルゴ リズムは，O(Δm)時間で求められることが分かっている．そこで，本研究では このSchrijverのアルゴリズムを計算機プログラムとして実装し，理論的に 導かれた計算時間と実際の計算時間を比較検討する．また，アルゴリズムの 性能も評価する． 2. Schrijverの辺彩色アルゴリズム Schrijverの辺彩色アルゴリズムの主要な部分は，枝数mのk-正則グラフの完全 マッチングをO(km)で求めるアルゴリズムである．まず，完全マッチングを求 めるアルゴリズムを示す． 完全マッチングアルゴリズム Input: k-正則２部グラフG=(V,E) Output: 完全マッチング Step 1: すべての枝の重みw(e):=1とする．任意のF⊆Eについて， w(F):=Σe∈F w(e) Step 2: Ew={ e∈E |w(e)>0 }の枝のみで構成される閉路Cを見つける. あればStep 3へ，なければ終了． Step 3: マッチングMとマッチングNで，C=M∪Nと分解する．(ただし，w(M)≧w(N)) w:=w+χ^{M}-χ^{N}と更新．Step 2に戻る． 定理 1: k-正則２部グラフに対する完全マッチングは，O(km)時間で求めることができる． 完全マッチングを利用し，辺彩色アルゴリズムを構築する． k-正則２部グラフに対する辺彩色アルゴリズム Input: k-正則２部グラフG=(V,E) Output: k-辺彩色 Step 1: 次数kが奇数ならStep 2へ，偶数ならStep 3へ．k=0になれば終了． Step 2: マッチングMを見つけて１色割り当てる．グラフからMを削除する． k=k-1として，Step 1に戻り，残りを彩色する． Step 3: オイラー路を見つけてグラフGを２つの1/2k-正則２部グラフ G1=(V,E1)とG2=(V,E2)に分ける．G1,G2を再帰的に彩色し，結果を合 わせてGの彩色とする．終了． 補題 2: k-正則２部グラフに対するk-辺彩色は，O(km)時間で求められる． ２部グラフに対する辺彩色アルゴリズム Input: ２部グラフG=(V,E) Output: 辺彩色 Step 1: 最大次数をkとする． Step 2: 各点の次数が1/2k以下の点があれば，Step 3へ．そうでなければStep 4へ． Step 3: 次数が1/2k以下の点同士を同じ側なら併合して１つの点にする． Step 4: 各点の次数と最大次数との差を調べ，次数をkにするようコピーと 並行枝を付け足して結ぶ． Step 5: k-辺彩色を求める． 補題 3: ２部グラフG=(V,E)に対するΔ(G)-辺彩色は，O(Δ(G)m)時間で求められる． 3. 計算機実験および結果 提案されたアルゴリズムをC言語により計算機プログラムとして実装した． 実験結果によると，計算時間はkmに比例していることが分かる．また 同じ次数に注目すると，計算時間はkmに比例している． 4. まとめ 本研究は，Schrijverのアルゴリズムに注目し，計算機プログラムとして実装した． その結果，２部グラフに対する辺彩色が非常に高速に求まることが分かり， その実用的な性能の高さを確認できた． 参考文献 [1] A. Schrijver: Bipartite edge coloring in O(Δm)time, SIAM Journal on Computing, 28 (1998) 841- 846. |
|||