6カラーグラフ頂点カラーアルゴリズム

Question

私はC++で、最大6色の平面グラフの頂点を色付けするアルゴリズムを作成しようとしています。私はちょっと擬似コードを探していました。どんな助けもありがとうございます。ありがとう。

Answer 1

参照：

デビッドMatula、ヨッシShiloachによってFIVE-COLORING A平面グラフ 、ロバート・タージャン

（ただ、GoogleのこのFOR TWO線形時間アルゴリズムとあなたがのPDFを見つけることができます紙）。

これは、O（n）時間に平面グラフを5色描く紙ですが、6色のアルゴリズムの簡単な説明から始まります。ここに重要なエキスがあります（書式の謝罪、これは単なるPDFのスクレープです）：

アロギー6カラー。隣接リスト 形式のn頂点平面グラフGが与えられた場合、このアルゴリズムはGの6色を決定する。ステップ1. [確立する 度リスト]各jについて、0-j-n-1は二重に< <リンクされた 次数jのGのすべての頂点のリスト。 - ステップ2. [頂点のラベルの最小次数] i = n、n - 1、n * - 1 ,. 。 。 、1は非真空j度の第1の頂点を頂点t/iとして最小のjのリスト を指定する。 j度のリストからviを削除します。 Gのtliに隣接していて、 度数リストに残っている各頂点U 'について、jr度リストからuを削除し、uを' j9 - 1度リストに挿入します。ステップ3. [色の頂点] i = 1,2の場合。 。 。 、 n、頂点tを割り当てる）i最も近い色の値（ の整数は1から6の間の整数でなければならない）は、すでに着色されている t）iに隣接する頂点で発生しない。