Федоров В.Н. - Введение в теорию графов, страница 7

П
олучим

Выбираем строку 4. Записываем

П
реобразуем матрицу

Выбираем строку 1. Записываем

Преобразуем матрицу

П
реобразование матрицы закончено – во всех строках и столбцах только нули.

Формируем произведение

П = С₁ С₂ С₄ = .

После раскрытия скобок и минимизации получаем

П = .

Обозначим

П = K₁ K₂ K₃ K₄ .

Дополняющие множества вершин , , , образуют семейство независимых множеств

= , = , = , ={ .

Число внутренней устойчивости графа α(G) = 3.

8.3. Раскраска вершин графа

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

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

Составим таблицу покрытий вершин графа внутренне устойчивыми множествами (табл. 8.1). Таблица строится следующим образом.

Число строк таблицы равно мощности семейства НМВ, каждая строка обозначается именем соответствующего независимого множества вершин, число столбцов равно числу вершин графа и столбцы обозначаются именами вершин, элемент таблицы a_i,j = 1, если вершина x_j входит в множество , иначе a_i,j = 0 (нули можно не писать).

Таблица 8.1

	x1	x2	x3	x4	x5	x6
			1		1	1
		1			1	1
	1		1			1
	1		1	1

Из таблицы видно, что для окраски вершины x₁ нужна краска множества или , для окраски вершины x₂ нужна краска множества , для вершины x₃ – нужна краска множества или , или и т.д.

Для окраски всех вершин нужны краски множеств, определяемых выражением

П’ = ( ) ( ) ( )( ).

После раскрытия скобок и минимизации получаем

П’= .

Количество элементов в П’ определяет число красок, необходимых для такой раскраски вершин, при которой смежные вершины имеют разные цвета.

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

Для данного примера (G) = 2. Вершины, входящие в , окрашиваются одной краской, например, красной (к). Вершины, входящие в , другой – белой (б). Раскраска показана на рис. 8.1.

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

Процедура определения хроматического числа оказалась достаточно сложной. В связи с этим возникает вопрос: – А нельзя как–то по проще хотя бы оценить это число?

Ясно, что для полного графа с n вершинами (K_n) = n, так как в полном графе каждая вершина смежна со всеми другими вершинами графа. Очевидно также, что (G) = 1, когда имеем нуль граф, в котором нет связей между вершинами. О хроматическом числе произвольного графа G можно только сказать, что оно лежит в пределах r (G) n, где r – число вершин максимального полного подграфа (такой подграф называется кликой), содержащегося в графе G.

Если известны степени вершин графа, то

(G) = maxdeg(G) + 1, (*)

где maxdeg(G) – максимальная степень вершин графа.

Для планарных графов получена оценка (G) 5, хотя существует гипотеза о возможности раскраски любого планарного графа не более чем четырьмя красками. Однако эта гипотеза еще не доказана.

(О планарных графах см. Раздел 11.)

Замечание. Если учесть оценку (*), то получается, что у планарного графа максимальная степень вершин не превосходит 4.

8.4. Алгоритм последовательной раскраски вершин графа

В простейшем случае последовательная раскраска вершин производится так:

1. Произвольной вершине a₁ графа G присвоить цвет 1.

2. Если вершины a₁,…, a_i раскрашены в цветов, то новой произвольно взятой вершине a_i+1 присвоить цвет, не использованный при раскраске ближайших соседей.

Для некоторых классов графов последовательная раскраска минимальна. В общем случае это не так.

Более точная последовательная раскраска производится с помощью приближенного алгоритма поиска МНМВ и сводится к следующему:

1. С помощью приближенного алгоритма в заданном графе находим МНМВ. Вершины этого множества окрашиваем краской 1.

2. Удаляем из графа окрашенные вершины и инцидентные им ребра.

3. В полученном подграфе находим МНМВ и его вершины окрашиваем краской 2.

4. Удаляем из графа окрашенные вершины и инцидентные им ребра и т.д., пока не окрасим все вершины графа.

8.5. Приближенный алгоритм поиска МНМВ

В этом алгоритме используется функция предпочтения

,

где Гv – множество вершин, смежных с v.

В основу функции предпочтения положены следующие соображения:

• в МНМВ выгоднее включать вершины с малыми степеням (у них мало смежных вершин);

• вершины, смежные с включаемыми в МНМВ, должны иметь максимально возможные степени.

Алгоритм поиска МНМВ:

Имеем граф G(V,E).

Обозначим максимальное независимое множество вершин графа через S, множество вершин, смежных с вершинами из S, обозначим через ГS.

1. Положим S = . Определим для всех вершин графа значения функции предпочтения.

2. Добавляем к S вершину v, имеющую минимальное значение функции предпочтения (если таких вершин несколько, то любую из них).

3. Проверяем Если ДА, то КОНЕЦ, иначе повторить п. 2.

Пример. Имеем граф G(6,6) рис. 8.2. Определить МНМВ.

V = {1, 2, 3, 4, 5, 6},

S = .

Определяем значения функции предпочтения:

S = {1},

S = {1, 3},

S = {1, 3, 4},

S = {1, 3, 4, 6}, КОНЕЦ.

Р
исунок 8.2

Множество S = {1, 3, 4, 6} и есть максимальное независимое множество вершин графа.

8.6. Реберная раскраска графа

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

Для реберной раскраски имеется достаточно точная оценка требуемого числа красок в виде

,

где максимальная степень вершин графа G.

Число красок, необходимое для реберной раскраски, при которой смежные ребра имеют разный цвет, обозначается и называется хроматическим классом или хроматическим индексом.

Для некоторых видов графов хроматический класс определяется достаточно просто, например, для графа в виде цикла с n вершинами 2 или 3 в зависимости от того, четно n или нечетно. Для двудольных полных графов = max(m, n). Для полных графов = n, если n нечетно, и = n – 1, если n четно.

Для раскраски ребер графа рис. 8.2 требуется 3 краски. Раскрасьте граф самостоятельно.

8.7. Контрольные вопросы

1. Поясните понятие внутренней устойчивости вершин графа.

2. Число внутренней устойчивости графа – что это такое и как оно обозначается?

3. Приведите алгоритм определения внутренне устойчивых множеств вершин графа.

4. Что такое вершинная раскраска графа? Приведите алгоритм определения минимального числа красок для такой раскраски.

5. Что такое хроматическое число графа и какие оценки существуют для него?

6. На чем основан приближенный алгоритм нахождения максимального независимого множества вершин графа?

7. Примените простейший алгоритм последовательной раскраски вершин графа на примере графа C₅. Сколько потребовалось красок? Сколько потребуется красок для раскраски графа C₆? Какой вывод можно сделать о раскраске графов–циклов?

8. Что такое хроматический класс графа и какие оценки существуют для него?

9. Связность графов

При исследовании графов возникает два вида задач на связность

• определение компонент связности графа,

• определение компонент сильной связности орграфа.

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

9.1. Определение компонент сильной связности орграфа

Подграф G’ орграфа G(V,E) называется максимальным сильно связным, если не существует сильно связного подграфа G”, строго содержащего G’.

Максимальные сильно связные подграфы орграфа G называются его компонентами сильной связности.

Вершины компонент сильной связности образуют множество классов эквивалентности C, |C| = p так, что

Принадлежность вершины x_i классу Cx_i определяется наличием маршрутов (x_i, x_j) и (x_j, x_i) для любой пары вершин.

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

Определим транзитивное замыкание в графе для вершины x_i

,