Раскраска графа

Пример

Задана матрица смежности графа. Найти разложение графа на компоненты сильной связности.

На рис.4 показана матрица смежности графа и заполнение столбца и строки , которым соответствует прямое и обратное транзитивное замыкание: ={1,2,3,4,5}, ={1,2,3} и компонента сильной связности ={1,2,3}. После вычеркивания столбцов и строк матрицы смежности с номерами 1,2,3, вошедшими в , рассматривается остаток матрицы, столбец и строка заполняются. В результате получается прямое и обратное транзитивное замыкание и компонента сильной связности: ={4,5}, ={4,5}, ={4,5}.

x

x

x

x

				x	X	x	x
						x	x

Рис.4

Рассмотрение элементов матрицы, оставшихся после вычеркивания столбцов и строк с номерами 4 и 5 дает такие результаты: ={6,7}, ={6,7}, ={6,7}.

Таким образом, представленный граф имеет 3 компоненты сильной связности: , , .

Задача раскраски состоит в раскрашивании вершин (ребер) графа так, чтобы любые две смежные вершины были окрашены в разный цвет, причем количество цветов должно быть минимально возможым. Обычно при раскраске цветам присваивают номера. Минимально возможное число разных цветов называется хроматическим числом графа. Для определения хроматического числа на практике используют приближенные методы, одним из которых является метод построения функции Гранди на графе.

Если необходимо раскрасить вершину Vj графа, смежную с вершинами Vk,Vl,Vm, уже выкрашенными в цвета с номерами 0,1,3, то вершина Vj красится в цвет, номер которого минимален и не равен номерам цветов вершин, смежных с Vj. В рассмотренном примере вершину Vj нужно покрасить в цвет 2. Вышеизложенное определяет смысл функции Гранди, а общий алгоритм раскраски графа с ее помощью состоит в следующем:

1) на графе выбирают произвольную вершину и окрашивают в цвет, номер которого минимален;

2) выбирают вершину, смежную с окрашенной, и красят ее в цвет, номер которого минимален и не равен номеру цвета окрашенной вершины;

3) находят вершину графа, смежную с окрашенными, и красят ее в цвет, номер которого минимален и не равен номерам окрашенных вершин;

4) если смежных вершин нет, возвращаются к п.1, в противном случае конец.

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

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

Дата добавления: 2017-01-13