раскраска графа ровно k цветами - PullRequest
Новая
       45

раскраска графа ровно k цветами

0 голосов
/ 03 июня 2018

Рассмотрим граф G (V, E) с V вершинами и E ребрами.Мы хотим раскрасить граф вершин точно в цвет K.

Раскраска графа означает присвоение цвета каждому узлу таким образом, чтобы две соседние вершины не имели одинаковый цвет.

Как мы можемреализовать этот вопрос?

1 Ответ

0 голосов
/ 27 июня 2018

Прежде всего, обратите внимание на предположение 2:

  1. If | V | k.
  2. Если мы можем раскрасить график меньше, чем k color и | v |> k тогда это возможно также с точно k цветом - мы можем просто переключить повторяющийся цвет на тот, который мы еще не использовали.

Мы можем использовать жадный алгоритм для решения этой проблемы.

Давайте присваиваем каждому цвету номер [1,2, ..., k] - пусть u представляет цвет i с помощью Ci.Начните с произвольного узла v1 и назначьте ему C1.Теперь давайте запустим BSF на графике для каждого узла и выберите минимальный цвет, который не существует в его узле настройки - если другой узел не имеет цвета, игнорируйте их.Если d (v)> k и все его настройки выполнены в другом цвете, верните false.

Псевдокод: 

// v.color init as 0 for all V
Queue <- new Queue(V1)
While Queue not empty:
    current <- Queue.pop
    if (current.color != 0 )
         continue
    adj <- v1.getAdj()
    min = 0
    for each adj:
         min = min(min, adj.color) 
    current.color <- C[min + 1]
    Queue.insert(adj)
...