Алгоритм раскраски графа

Question

из вики http://en.wikipedia.org/wiki/Graph_coloring

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

С учетом 'n' цветов и 'm' вершин, как легко можно раскрасить граф Алгоритм быть реализован на языке программирования?

Язык без барьеров.

Просто головоломка.

(Предположим, существуют объекты Graph и вершины)

Edit:
После прочтения вики проблема NP-полная
Время пересмотреть книги по математике:)
мой плохой.
извините.

Просто любопытно,
Это было опробовано? как при написании программ для таких же?
Я слышал, что это используется в оптических сетях?

Разве это не похоже на раскраску куба ??
(минимальное количество цветов для окраски граней куба, чтобы две стороны не имели одинаковый цвет?)

Answer 1

Это полная проблема NP, прочитайте запись Википедии для получения дополнительной информации о различных методах решения.

Answer 2

Если вам дано 2 цвета, а график 2-раскрашен (т.е. это двудольный граф ), то вы можете сделать это за полиномиальное время довольно тривиально.

Я дал псевдокод в качестве ответа на этот вопрос: Алгоритм раскраски графиков: типичная проблема планирования .

Answer 3

В магистерской работе я тестирую алгоритмы раскраски. Самый простой алгоритм - Edge Backtrace .

Это моя реализация в Java :

public boolean edgeBackTrace (List<Edge<T>> edgesList, Map<Edge<T>, List<Edge<T>>> neighborEdges) {
  for (Edge<T> e : edgesList) {
    e.setColor(0);
  }
  int i = 0;
  while (true){
    Edge<T> edge = edgesList.get(i);
    edge.setColor(edge.getColor() + 1);
    if (edge.getColor().equals(4)) {
      edge.setColor(0);
      if (i == 0) {
        return true;
      } else {
        i--;
      }
    } else {
      boolean diferentColor = false;

      for (Edge<T> e : neighborEdges.get(edge)) {
        if (e.getColor().equals(edge.getColor())) {
          diferentColor = true;
        }
      }

      if (diferentColor == false) {
        i++;
        if (i == edgesList.size()) {
          return false;
        }
      }
    }
  }
}

Алгоритм возвращает значение true, если график имеет раскраску. Вы можете видеть в dgeList в качестве цвета отдельные ребра.

Answer 4

Как уже упоминалось, общая проблема является np-полной.Двудольные графы можно раскрасить, используя только 2 цвета.

Также верно, что плоские графы (графы, которые не содержат K3,3 или K5 в качестве подграфов, согласно теореме Куратовского) могутбыть окрашенным в 4 цвета.