Dサター

DSatur は、 1979 年にDaniel Brélazによって提案されたグラフ着色 アルゴリズムです。 ^[1]貪欲着色アルゴリズムと同様に、DSatur はグラフの頂点を1 つずつ着色し、必要に応じて未使用の色を追加します。新しい頂点が着色されると、アルゴリズムは残りの着色されていない頂点のうち、その近傍に最も多くの色がある頂点を決定し、次にその頂点を着色します。Brélaz はこの数を、特定の頂点の飽和度と定義しています。^[1]「飽和度」という用語の短縮形がアルゴリズムの名前になっています。^[2] DSatur は、ヒューリスティックなグラフ着色アルゴリズムですが、2 部グラフ、^[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 で、最も「制約」されていると思われる頂点が最初に色付けされる点にあります。

右に示すグラフを考えてみましょう。これはホイール グラフなので、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年のLewisによる実験的比較では、DSaturは、エッジ確率を持つランダムグラフ上で貪欲アルゴリズムよりも大幅に優れた頂点彩色を生成しましたが、再帰最大優先アルゴリズムよりも大幅に劣った彩色を生成しました。^[2]${\displaystyle p=0.5}$

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