Теория графов - хроматический индекс - PullRequest
Новая
       8

Теория графов - хроматический индекс

8 голосов
/ 26 мая 2011

Я должен создать программу, которая скажет, является ли граф d раскрашиваемым или нет - в основном я должен проверить, равен ли хроматический индекс d или d + 1, где d - максимальная степень всех вершин (теорема Визинга).Я знаю, что эта проблема является NP-полной, и в основном она должна быть грубой.У меня была идея, но я не знаю, верна ли она -

1) найти вершину с deg (v) = d и закрасить все ребра, попадающие в v, с помощью d distnict цветов.

2) для всех ребер, инцидентных вершинам, смежным с v, примените цвет из набора d цветов

3) повторите 2) для "обнаруженных" ребер

Если все ребра окрашены с помощью dцвета, хроматический индекс - d, и у меня есть одна раскраска графа G.

Если какой-либо край не может быть окрашен цветом из набора из d цветов, раскрасьте его цветом d + 1-й и оставшиеся края цветас цветами из набора цветов d + 1 - вот вопрос - используя эту схему, если я объявляю, что хроматический индекс равен d + 1, есть ли вероятность, что с какой-либо другой раскраской хроматический индекс будет d?(для каждого ребра, который будет окрашен, я выбираю один цвет, который можно использовать) ..

Кроме того, какое графическое представление будет лучшим для этой проблемы?Во входном файле граф записывается в матрице смежности.я знаю, что это можно решить с помощью рекурсии, но я понятия не имею, как.Я застрял с некоторыми слишком сложными идеями: 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;
}

Ответы [ 2 ]

2 голосов
/ 04 января 2013

Создайте ограничения для каждого ребра, назначьте разные цвета всем ребрам вершины с наибольшим числом ребер, а затем обработайте каждое ребро от самого ограниченного ребра. 

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)

Возможно, было бы неплохо определить наиболее ограниченный край как край с наиболее окружающими краями, которым уже были назначены цвета, но это может привести к значительным накладным расходам.

0 голосов
/ 06 июня 2011

преобразование вашего графа для использования алгоритма раскраски вершин довольно просто: для каждого ребра (x, y) в исходном графе создайте вершину xy в преобразованном графе, идля каждой вершины x в исходном графе создайте ребра между всеми вершинами преобразованного графа, содержащие в своем имени x .

Cheers

...