8

グラフが d colorable かどうかを判断するプログラムを作成する必要があります。基本的には、彩色インデックスが d または d+1 であるかどうかを確認する必要があります。ここで、d はすべての頂点の最大次数です (vizing の定理)。この問題はNP完全であり、基本的にブルートフォースでなければならないことを私は知っています。アイデアはあったが、それが正しいかどうかわからない -

1) deg(v) = d で頂点を見つけ、v に付随するすべてのエッジを d の異なる色で色付けします。

2) v に隣接する頂点に付随するすべてのエッジに対して、d 色のセットからいくつかの色を適用します。

3) 「発見された」エッジに対して 2) を繰り返す

すべてのエッジが d 色で着色されている場合、彩度インデックスは d であり、グラフ G の 1 つの着色があります。

いくつかのエッジを d 色のセットの色で着色できない場合は、d+1 番目の色で色を付け、残りのエッジを d+1 色のセットの色で色付けします - ここに問題があります - このスキームを使用して、クロマティック インデックスが d+1 であると宣言した場合、他の着色でクロマティック インデックスが d になる可能性はありますか? (色付けされるエッジごとに、使用できる色を 1 つ選択しています)..

また、この問題に最適なグラフ表現はどれですか? 入力ファイルでは、グラフは隣接行列で記述されます。再帰で解決できることは知っていますが、方法がわかりません。私はいくつかの複雑すぎるアイデアで立ち往生しています:S (いくつかのヒントまたは擬似コードをいただければ幸いです)。

編集：

思いついたのですが、大丈夫だと思います（純粋なブルートフォース）。私はまだこれを実装しようとしませんでした。何か間違っているところがあればコメントしてください。もう一度言います - アルゴリズムは、グラフが d または d+1 色で色付け可能かどうかをチェックする必要があります。d は、与えられた単純なグラフのすべての頂点の最大次数です。

colorEdge(edge, color, extra) {
    if (edge colored) return;  //if already colored, return
    if (can be colored in color) color it; //if color can be applied, apply it
    else {
        //else, 'd+1'-st color neded, so color it with that color, continue finding 
        //coloring with d+1 colors
        extra = true; 
        color it in color extra;
    }

    //recursivly try to color adjacent edges with available colors
    for each color c' from set of d colors {
        for each edge k adjacent to current {
            colorE(k, c', extra)
        }
    }
}

//main
bool extra = false;
for each color b from set of d colors {
    colorEdge(some starting edge, b, extra)
    if (!extra) break;
}
4

2 に答える 2

2

各エッジの制約を生成し、最も多くのエッジを持つ頂点のすべてのエッジに異なる色を割り当ててから、最も制約されたエッジから各エッジを処理します。

for each edge e1
for each edge e2
  if (e1 and e2 have a common vertex)
    e1.addConstaint(can't match e2's colour)
    e2.addConstaint(can't match e1's colour)

vertex v = vertex with most edges
if (v has more edges than colours we have available) STOP
assign each edge of v a different colour

Sort edges by number of constraints
Remove all edges connected to v (thus assigned a colour)

process(edge) :=
  while (haven't tried all colours within the constraints)
    edge.colour = next untried colour within the constraints
    process(next most constrained edge)

process(most constrained edge)

最も制限されたエッジを、既に色が割り当てられている周囲のエッジが最も多いものとして定義することは良い考えかもしれませんが、これはかなりのオーバーヘッドを引き起こす可能性があります。

于 2013-01-04T18:31:25.913 に答える
0

頂点カラーリング アルゴリズムを使用するようにグラフを変換するのは非常に簡単です。元のグラフの各エッジ(x,y) に対して、変換されたグラフの頂点xyを作成し、元のグラフの各頂点x に対して、グラフ内のすべての頂点間にエッジを作成します。名前にxを含む変換されたグラフ。

乾杯

于 2011-06-06T06:35:34.957 に答える