Один алгоритм раскраски графа

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

Алгоритм

  1. Построить первоначальную раскраску (необязательно правильную). Эвристика: построить раскраску в два цвета поиском в ширину (чётный фронт → цвет «0», нечётный фронт → цвет «1»).
  2. Пока есть конфликты, производить разрешение конфликтов.

Под конфликтами понимается наличие одинаково окрашенных вершин-соседей. Проверка «есть конфликты» перебирает все вершины и составляет список C троек (вершина v, количество конфликтов n, минимальный неконфликтный цвет c), отвечающий конфликтующим вершинам (n = количество соседей v, имеющих тот же цвет, что и v). Если вершину v перекрасить в цвет c, то конфликт будет разрешён (при условии сохранения прежних цветов соседями v). Если конфликтов нет, то список C будет пуст, и алгоритм закончит работу — будет получена правильная раскраска вершин графа.

«Разрешение конфликтов» производится следующим образом.

  1. Завести множество соседей перекрашенных вершин A := Ø.
  2. Упорядочить список конфликтов C по убыванию числа конфликтов n.
  3. Для каждой тройки (v, n, c) из C, если v не принадлежит A, то:
    1. Назначить вершине v цвет c.
    2. Пополнить A соседями v.

Свойства алгоритма

По завершении работы алгоритма получаем правильную вершинную раскраску. Необходимо доказать, что работа алгоритма завершится. Строгого доказательства я выполнять не стал. Однако, нетрудно заметить, что всего конфликтов может быть не больше, чем всего вершин в графе (N), за одно разрешение конфликтов разрешается как минимум один конфликт и не добавляется новых, поэтому достаточно N итераций цикла. Одна итерация цикла требует O(N + M) действий (для каждой вершины проверить всех её соседей). Отсюда можно сделать вывод, что алгоритм имеет сложность O(N(N + M)) ≤ O(N3).

Реализация

Была написана реализация алгоритма на C++, включающая набор простых графов для проверки. Для всех простых тестов алгоритм даёт оптимальную раскраску.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: