Monthly Archives: Июль 2012

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

В этой записи я решил представить алгоритм, придуманный мной под впечатлением от распределённых (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++, включающая набор простых графов для проверки. Для всех простых тестов алгоритм даёт оптимальную раскраску.

Реклама

YAPLC: mainstream generations

It seems to me it was this way (in «industrial mainstream»).

60‘ ad-hoc calculations, procedural programming (Fortran)
70‘ standardized, structural programming, databases (COBOL, PL/I)
80‘ portable assembly, system programming, libraries, 4GL, micros boom (C, Pascal, SQL, Basic)
90‘ object-based/oriented programming (C++, VB, Object Pascal)
00‘ managed static-typed languages, heavily-OO frameworks (Java, C#)
10‘ dynamic-typed languages, still mostly OOP-like (Python, Ruby, JS)
20functional programming? asynchronous/massive parallelism? native code renaissance?

What languages will see mainstream use in 20’s? Probably, it will be «hybrids» based upon current ones (and possibly bearing the same names).