DSatur

DSatur

クラス	グラフ彩色
最悪の場合の空間計算量	Ο ( n ^2 )

DSaturは、 1979年にダニエル・ブレラズによって提唱されたグラフ彩色アルゴリズムです。^{[ 1 ]}貪欲彩色アルゴリズムと同様に、DSaturはグラフの頂点を1つずつ彩色し、必要に応じて未使用の色を追加します。新しい頂点が彩色されると、アルゴリズムは残りの未彩色頂点のうち、近傍の色数が最も多い頂点を決定し、次にその頂点を彩色します。ブレラズはこの数値を、与えられた頂点の彩度（degree of saturation ）と定義しています。 ^{[ 1 ]}「彩度（degree of saturation）」という用語の短縮形が、このアルゴリズムの名前の由来です。^{[ 2 ]} DSaturはヒューリスティックなグラフ彩色アルゴリズムですが、二部グラフ、^{[ 1 ]}サイクルグラフ、ホイールグラフに対して正確な結果を生成します。^{[ 2 ]} DSaturは、文献では彩度LFとも呼ばれています。^{[ 3 ]}

擬似コード

頂点の「彩度」を、その近傍で使用されている異なる色の数とします。頂点集合と辺集合からなる単純な無向グラフ が与えられた場合、アルゴリズムは色ラベルを使用してすべての頂点に色を割り当てます。アルゴリズムは次のように動作します。^{[ 4 ]}${\displaystyle G}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle 1,2,3,...}$

1. 最も彩度の高い無彩色頂点を とします。同点の場合は、無彩色頂点から誘導される部分グラフの次数が最大の頂点を選択します。${\displaystyle v}$ ${\displaystyle G}$
2. 隣接するどの色ラベルにも使用されていない最も低い色ラベルに割り当てます。${\displaystyle v}$
3. すべての頂点が色付けされている場合は終了し、そうでない場合は手順 1 に戻ります。

このアルゴリズムのステップ2では、貪欲彩色アルゴリズムと同じ手法を用いて頂点に色を割り当てます。2つのアプローチの主な違いは、上記のステップ1で、最も「制約」されていると判断された頂点が最初に色付けされるという点にあります。

例

7つの頂点と12の辺を持つ車輪グラフ

右に示すグラフを考えてみましょう。これは車輪グラフなので、DSaturアルゴリズムによって最適に色付けされます。アルゴリズムを実行すると、以下のように頂点が選択され、色付けされます。（この例では、DSaturの両方のヒューリスティックで同点が発生した場合、これらの頂点の中で最も辞書式ラベルの低い頂点が選択されます。） ${\displaystyle G=(V,E)}$

1. 頂点（色1）${\displaystyle g}$
2. 頂点（色2）${\displaystyle a}$
3. 頂点（色3）${\displaystyle b}$
4. 頂点（色2）${\displaystyle c}$
5. 頂点（色3）${\displaystyle d}$
6. 頂点（色2）${\displaystyle e}$
7. 頂点（色3）${\displaystyle f}$

これにより、最終的な 3 色のソリューションが得られます。 ${\displaystyle {\mathcal {S}}=\{\{g\},\{a,c,e\},\{b,d,f\}\}}$

パフォーマンス

DSaturの最悪ケースの計算量は です。ここではグラフの頂点数です。これは、次に色を付ける頂点を選択するプロセスに時間がかかり、このプロセスが 回実行されるためです。このアルゴリズムは、飽和度を格納するためにバイナリヒープを使用して実装することもできます。バイナリヒープは で動作します。または、フィボナッチヒープは で動作します。 ^{[ 2 ]}これにより、疎グラフでの実行速度が大幅に向上します ${\displaystyle O(n^{2})}$ ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle O((n+m)\log n)}$ ${\displaystyle O(m+n\log n)}$ ${\displaystyle m}$

^{DSaturは二部グラフ[ 1 ]}だけでなく、サイクルグラフやホイールグラフでも正確であることが知られています。 ^{[ 2 ]} 2021年のルイスによる実験的比較では、DSaturは、エッジ確率を持つランダムグラフ上で貪欲アルゴリズムよりも大幅に優れた頂点彩色を生成しましたが、一方で再帰最大優先アルゴリズムよりも大幅に劣った彩色を生成しました。^{[ 2 ]}${\displaystyle p=0.5}$

参考文献

1. ブレラズ、ダニエル (1979-04-01). 「グラフの頂点を色付けする新しい方法」 . Communications of the ACM . 22 (4): 251– 256. doi : 10.1145/359094.359101 . ISSN  0001-0782 . S2CID  14838769
2. Lewis, RMR (2021).グラフカラーリングガイド：アルゴリズムとアプリケーション. コンピュータサイエンステキスト（第2版）. ベルリン: Springer. doi : 10.1007/978-3-030-81054-2 . ISBN 978-3-030-81053-5. S2CID  57188​​465 .
3. Kubale編 (2004). Graph Colorings (Vol.352) . プロビデンス：アメリカ数学会. p. 13. ISBN 978-0-8218-3458-9。
4. Lewis, Rhyd (2019-01-19). 「グラフ着色のための構成的アルゴリズム」 . youtube.com . イベントは3:49に発生します

外部リンク

• GCol DSaturを搭載したグラフカラーリング用のオープンソースPythonライブラリ
• 高性能グラフ カラーリング アルゴリズム 『A Guide to Graph Colouring: Algorithms and Applications 』 (Springer International Publishers、2021 年)で使用されているグラフ カラーリング アルゴリズムのスイート (C++ で実装)
• DSatur アルゴリズムの C++ 実装。記事「グラフ カラーリングのための DSatur アルゴリズム」の一部として発表。Geeks for Geeks (2021)