Числа внутренней и внешней устойчивости графа

Рассмотрим теперь число внутренней устойчивости. Если две любые вершины подмножества X’ графа G = (X, U), X’ Í X не смежны, то оно называется внутренне устойчивым. Подмножество y _i Í X графа G = (X, U) называется максимальным внутренне устойчивым подмножеством (МВУП) или независимым (НП), если добавление к нему любой вершины x_i Î X делает его не внутренне устойчивым. Подмножество y _i будет независимым, если

                                      " x_i Î y _i (Г x_i Ç y _i = Æ).                         (17.8)

Независимые подмножества различаются по числу входящих в них элементов. В произвольном графе G можно выделить семейство всех НП вида y = {y₁, y₂,..., y _s }. Независимые подмножества, содержащие наибольшее число элементов, называются предельными. Тогда число внутренней устойчивости h(G) определяется мощностью предельного НП

                                     h(G) = |max y _i |, y _i Î y.                           (17.9)

Число внутренней устойчивости h(G) можно связать с хроматическим числом c(G) следующим образом: h(G)c(G) ³ n.

Рассмотрим вопросы построения семейства независимых подмножеств на основе матрицы смежности или ее списка. Данный алгоритм описан А. Кофманом на основе идей предложенных К. Магу. Идея алгоритма построения семейства y = {y₁, y₂,..., y _l } заключается в следующем. В списке смежности графа G определяется строка, имеющая наибольшее число элементов. Если таких строк несколько, то выбирается любая. Для определенной строки i записывается элемент C _i = (x_i + x_k × x_l ×... × x_q), (где знак сложения “ x_i + x_k ” — подразумевает операцию дизъюнкции, а знак умножения “ x_k × x_l ” или “ x_k x_l ” – операцию конъюнкции). Здесь x_i – вершина графа, соответствующая выделенной строке i, а x_k, x_l,..., x_q – вершины, смежные с x_i. Далее в списке смежности исключается строка i, а также элементы с индексом i из всех оставшихся строк списка. Указанная операция соответствует выделению из графа G звездного подграфа с вершиной x_i. В списке снова определяется строка j с наибольшим числом элементов и записывается элемент C _j = (x_j + x_p × x_r ×... × x_v). Далее процесс выполняется аналогично до тех пор, пока в списке для оставшихся строк не будет содержаться ни одного элемента. Затем составляется произведение П = C _i × C _j ×... × C _k, в котором раскрываются скобки, и в полученной сумме выполняется минимизация с учетом выражений

              x_i ⁿ = x_i, x_i + x_i +... + x_i = x_i; x_i + 1 = 1; x_i + x_i x_j = x_i.    (17.10)

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

Методика определения МНП используется для раскраски вершин графа G.

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

Если получено семейство МНП, то можно построить матрицу M = ||m _{i , j} ||_n×w, где

w – число МНП в семействе y. Тогда задачу раскраски сводят к нахождению наименьшего числа строк, покрывающих все ее столбцы единицами.

Например, для графа G (рис. 17.1) матрицу M можно записать следующим образом:

		x 1	x 2	x 3	x 4	x 5	x 6	x 7
M =	y1	1	0	0	0	1	1	1	.
	y2	1	0	0	1	0	0	0
	y3	0	1	0	0	0	1	0
	y4	0	1	0	1	0	0	0
	y5	0	0	1	1	0	0	0

Проанализировав данную матрицу, можно отметить, что минимальное число строк, покрывающих все столбцы матрицы, равно трем. Это строки y₁ (покрываются столбцы x ₁, x ₅, x ₆ и x ₇), y₅ (покрываются столбцы x ₃, x ₄), а также либо строка y₃ (покрываются столбцы x ₂, x ₆), либо строка y₄ (покрываются столбцы x ₂, x ₄).

Таким образом, можно выполнить следующую раскраску графа: вершины x ₁, x ₅, x ₆ и x ₇ – первый цвет; вершины x ₃, x ₄ – второй цвет; вершина x ₂ – третий цвет.

Рассмотрим алгоритм определения внешне устойчивого подмножества.

Пусть исследуемый объект задан в виде неориентированного графа G = (X, Г x), который можно рассматривать как пару, образованную множеством Х и многозначным отображением Г х множества Х в себя. Х = { x ₁, x ₂,..., x_n } – множество вершин графа, Г х _i = { x_k, x_e,..., x_p } определяет множество вершин x_k, x_e,..., x_p, смежных с вершиной x_i, другими словами, определяет ребра графа (x_i, x_k), (x_i, x_e),..., (x_i, x_p); .

Подмножество вершин M _i Í Х графа G называется внешне устойчивым, если

                                     (" x Ï M _i) (G x Ç M _i ¹ Æ).                    (17.11)

Внешне устойчивое подмножество (ВУП) называется минимальным, если удаление из него произвольной вершины делает его внешне неустойчивым. В каждом графе можно выделить семейство М = {M₁, M₂,..., M _i } минимально внешне устойчивых подмножеств (МВУП). Элементы семейства М отличаются друг от друга по виду и количеству входящих в них элементов. Мощность МВУП, содержащего наименьшее число вершин, называется числом внешней устойчивости (b(G)).

Рассмотрим алгоритм получения минимального внешне устойчивого подмножества и наметим путь получения семейства МВУП.

Для задания графов будем использовать структурные числа. Система А, не содержащая одинаковых столбцов a_i и одинаковых элементов a (q, i) в каждом столбце, называется структурным числом.

A = { a ₁, a ₂,..., a_n }, a_i ¹ a_j, a_q = { a (1, q), a (2, q),..., a (m, q)}; a (i, q) ¹ a(j, q).

Столбцам структурного числа (СЧ) можно поставить в соответствие покрывающие деревья графа, а элементам столбцов СЧ – номера соответствующих деревьев. СЧ А имеет геометрическое изображение в виде графа G = (X, Г x), Х = { x ₁, x ₂,..., x_n }, если существует разложение А на простые сомножители P₁, P₂,..., P _{n -1} и произвольный элемент a_i Î P _i встречается не более чем в двух сомножителях. Если каждый P _i записать в виде номеров ребер, смежных вершине x_i, то СЧ графа G примет вид А = P₁, P₂,..., P _{n -1}. Произведение элементов P _i позволит получить СЧ в виде матрицы, где каждый столбец соответствует номерам ребер покрывающего дерева.

Граф G будем задавать в виде преобразованного структурного числа (ПСЧ).

A = Q₁, Q₂,..., Q _n; Q _i = [ i ][ j ₁, j ₂,..., j_l ] = [ i ][Q’ _i ].

Сомножитель Q _i соответствует вершине x_i графа G; i – индекс x_i; Q’ _i = j ₁, j ₂,..., j_l – последовательность индексов вершин, смежных x_i.

Для графа G (рис. 17.7)

Рис 17.7. Граф G

преобразованное структурное число запишется следующим образом:

А =	[1]	[2, 3, 4, 5]	.
	[2]	[1, 5, 6]
	[3]	[1, 4, 7]
	[4]	[1, 3, 6]
	[5]	[1, 2, 7]
	[6]	[2, 4]
	[7]	[3, 5]

Очевидно, что такая запись идентична той, что получилась бы, если бы мы использовали списочное задание графа. Таким образом, преобразованное структурное число А (ПСЧ) это не что иное как список смежности рассматриваемого графа. При этом, для задания графа достаточно n – 1 строк вида Q _i. В связи с вышесказанным в дальнейшем при решении практических задач будем считать равнозначным обозначение A (т.е. преобразованное структурное число) и R_L (т.е. список смежности).

Введем понятие расширенной алгебраической производной ПСЧ, которую запишем следующим образом:

 – исключена строка Q _i, а также элементы i и j ₁, j ₂,..., j_l из Q’ _k частей оставшихся строк А.

Указанная операция соответствует удалению из графа G звездного подграфа с вершиной x_i, а также ребер, соединяющих вершины смежные x_i. Вершины, удаленные после взятия производной, будем записывать так: X’ = { i, j ₁, j ₂,..., j_l }. Причем X’ Í X.

На основе введенной операции взятия расширенной алгебраической производной сформулируем алгоритм построения минимального внешне устойчивого подмножества M _i Í M. Основная идея алгоритма заключается в следующем. В ПСЧ определяется строка Q _i, у которой |Q’ _i | максимальна. Если таких строк несколько, то выбирается любая. Далее определяется расширенная алгебраическая производная  и записывается подмножество X’ = { x_i, x_k, x_l,..., x_q } (вершины x_k, x_l,..., x_q соответствуют элементам Q’ _i). Затем производится сравнение Х с Х’. Если Х’ = Х, то вершина x_i образует внешне устойчивое подмножество M1. В противном случае в ПСЧ A’ снова определяется строка Q _j, у которой |Q’ _j | максимальна. Если таких строк несколько, то выбирается строка Q _s, которая имеет максимальное число элементов, не вошедших в подмножество Х’ на предыдущем шаге. Находится  и записывается подмножество X’’. Если X’’ = Х, то вершины x_i и x_j образуют внешне устойчивое подмножество M1 = { x_i, x_j }. Если нет, то процесс повторяется аналогично, пока на некотором l шаге X^{( l )} = X. Для построения семейства М необходимо аналогичные операции над ПСЧ выполнять последовательно с каждой строкой с просмотром всех ответвлений.

Запишем алгоритм построения минимального внешне устойчивого подмножества множества вершин G.

1°. Запись по графу G преобразованного структурного числа А.

2°. Выбор в А строки Q _i c |Q’ _i | = max.

3°. Определение  и получение Х’.

4°. Сравнение X’ с Х. Если |X’| = |X|, то М₁ = { x_i } и переход к 6°. Иначе к 5°.

5°. Выбор в ПСЧ строки j с максимальным Q’ _j, j: = i и переход к 3°.

6°. Выделено внешне устойчивое подмножество. Конец работы алгоритма.

Работу алгоритма покажем на примере графа G (рис. 17.7). В ранее записанном ПСЧ А выделим строку Q₁, т.к. часть Q’₁ содержит наибольшее число элементов. Определим  и получим новое ПСЧ

А’ =	[2]	[6]	.
	[3]	[7]
	[4]	[6]
	[5]	[7]
	[6]	[Æ]
	[7]	[Æ]

Выделенное подмножество – X’ = { x ₁, x ₂, x ₃, x ₄, x ₅}. Граф, соответствующий A’, показан на рис. 17.8.

Рис. 17.8. Преобразованный г раф G

Мощность X’ не равна мощности Х. Следовательно, вершину x ₁ относим в М₁ и продолжаем процесс получения внешне устойчивого подмножества. На втором шаге определяем строки Q₂, Q₃, Q₄, Q₅. Так как мощность этих строк одинакова, мы можем выбрать любую, например строку Q₂. После этого вычисляем  и получаем:

А’’ =	[3]	[7]	.
	[4]	[Æ]
	[5]	[7]
	[6]	[Æ]
	[7]	[Æ]

Теперь X’’ = { x ₁, x ₂, x ₃, x ₄, x ₅, x ₆}. Величина |X’’| ¹ |X|, следовательно, вершину x ₂ относим к М₁ и алгоритм продолжает работу. Рассматриваем строки Q₃ и Q₅. Выбираем любую из них, например Q₃, и определяем значение . В результате получим

А’’ =	[4]	[Æ]	.
	[5]	[Æ]
	[6]	[Æ]
	[7]	[Æ]

X’’’ = { x ₁, x ₂, x ₃, x ₄, x ₅, x ₆, x ₇, x ₈} = X. Следовательно, получили внешне устойчивое подмножество M = { x ₁, x ₂, x ₃}.

Теорема 17.2. Подмножество М _i, полученное по алгоритму, является минимальным внешне устойчивым подмножеством.

Доказательство. Покажем, что М _i есть внешне устойчивое подмножество. Предположим, что М _i не является внешне устойчивым, т.е. элементы подмножества вершин М _i совместно не смежны оставшимся вершинам графа. Это говорит о том, что на конечном l шаге работы алгоритма X^{( l )} ¹ X, что противоречит условию алгоритма. Так как алгоритм заканчивает работу, когда X^{( l )} ¹ X, то М _i является внешне устойчивым подмножеством.

Покажем теперь, что М _i Ì М является минимальным внешне устойчивым подмножеством. Предположим, что существует М _j такое, что М _j Ì М _i, т.е. существует, по крайней мере, один элемент x_b Î X, после удаления которого из М _i, подмножество М _j будет внешне устойчивым. Другими словами, алгоритм после получения внешне устойчивого подмножества продолжит работу и выделит М _i É М _j, что противоречит структуре алгоритма. Следовательно, М _i есть минимальное внешне устойчивое подмножество.

Для нахождения числа внешней устойчивости необходимо выделить семейство минимальных внешне устойчивых подмножеств и определить в нем наименьшее по мощности подмножество.

Существуют графы, которые содержат некоторое подмножество X’ Í X вершин, причем это подмножество является одновременно внутренним и внешне устойчивым. Подмножества такого типа называются ядрами графа.

Теорема 17.3 Если граф G = (X, U) имеет ядро, то его числа устойчивости удовлетворяет условию

                                                n(G) ³ b(G).                               (17.12)

Например, в графе G (рис 3.7) подмножество вершин { x ₃, x ₅, x ₆} является ядром, так как оно одновременно и внешне и внутренне устойчиво. Причем h(G)= 3 = b(G).

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Пример 1. Выделить семейство независимых подмножеств для графа, заданного списком смежности R_L.

.

Решение: для решения поставленной задачи воспользуемся вышеописанным алгоритмом.

1. Выбираем из списка смежности R_L строку с наибольшим числом элементов. В данном случае это строка с индексом 3.

Теперь можем записать следующее выражение:

C₃ = (x ₃ + x ₂ x ₅ x ₆ x ₇ x ₈).

Удаляем из списка 3-ю строку и из всех остальных строк – элементы с индексом 3. В результате получим модифицированный список смежности R_L1.

.

2. В списке R_L1 выбираем строку с индексом 4. Записываем выражение: C₄ = (x ₄ + x ₁ x ₅ x ₇ x ₈). После удаления четвертой строки и элементов с соответствующими ей индексами, получим список смежности R_L2.

.

3. Выбираем строку 2 и записываем выражение C₂ = (x ₂ + x ₁ x ₆ x ₇). После удаления второй строки и элементов с соответствующими ей индексами, получим список R_L3.

.

4. Из двух оставшихся ненулевых строк, выберем строку 1 и запишем C₁ = (x ₁ + + x ₅).

5. Запишем произведение полученных выражений:

P =(x ₁ + x ₅)(x ₂ + x ₁ x ₆ x ₇)(x ₃ + x ₂ x ₅ x ₆ x ₇ x ₈)(x ₄ + x ₁ x ₅ x ₇ x ₈).

В результате последовательного перемножения и минимизации на основе тождеств алгебры логики получим выражение:

P = x ₁ x ₂ x ₃ x ₄ + x ₁ x ₂ x ₃ x ₅ x ₇ x ₈ + x ₁ x ₃ x ₄ x ₆ x ₇ + x ₂ x ₃ x ₄ x ₅ + x ₁ x ₃ x ₅ x ₆ x ₇ x ₈ + + x ₁ x ₂ x ₅ x ₆ x ₇ x ₈.

6. Обозначим каждую конъюнкцию в произведении следующим образом: K₁, K₂, K₃, …, K₆. Теперь «проинвертируем» каждый элемент полученного произведения, т.е. определим элементы не входящие в каждую из конъюнкций:

 = x ₅ x ₆ x ₇ x ₈ + x ₄ x ₆ + x ₂ x ₅ x ₈ + x ₁ x ₆ x ₇ x ₈ + x ₂ x ₄ + x ₃ x ₄.

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

y = [y₁, y_2, y_3, y₄, y_5, y₆],

где y₁ = { x ₅, x ₆, x ₇, x ₈}; y₂ = { x ₄, x ₆}; y₃ = { x ₂, x ₅, x ₈}; y₄ = { x ₁, x ₆, x ₇, x ₈}; y₅ = { x ₂, x ₄}; y₆ = { x ₃, x ₄}.

Поскольку мощность максимального независимого подмножества равна четырём, то число внутренней устойчивости заданного графа h(G) также равно 4.

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

Пример 2. Выполнитьраскраску графа, заданного в примере 1 на основе алгоритма Кофмана. Выпишем для каждой вершины графа те конъюнкции, в которые эти вершины не входят.

x ₁ Ï K₄; x ₂ Ï K₃, K₅; x ₃ Ï K₆; x ₄ Ï K₂, K₅, K₆; x ₅ Ï K₁, K₃; x ₆ Ï K₁, K₂, K₄; x ₇ Ï K₁, K₄; x ₈ Ï K₁, K₃, K₄.

Теперь запишем полученное выражение в виде произведения этих конъюнкций:

P^‘ = K₄ × (K₃ + K₅) × K₆ × (K₂ + K₅ + K₆) × (K₄ + K₃) × (K₁ + K₂ + K₄) × (K₁ + K₄) × (K₁ + K₃ + K₄).

После перемножения элементов данного выражения и его минимизации получим следующее выражение:

P^‘ = K₁K₂K₃K₄K₆ + K₁K₄K₅K₆.

Число элементов K _i в каждой конъюнкции соответствует количеству цветов, которые необходимы для раскраски графа, а каждый K _i - определяет подмножество вершин, которые можно раскрасить одним цветом.

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

Рассмотрим, например, конъюнкцию, содержащую четыре элемента. Это элементы K₁, K₄, K₅, K₆.Как мы уже определили ранее, конъюнкции K₁ соответствуют элементы { x ₅, x ₆, x ₇, x ₈}.Следовательно, эти вершины мы окрашиваем в первый цвет.

Для определения вершин, которые будут окрашены во второй цвет необходимо определить разность:

K₄ \ K₁ = { x ₁, x ₆, x ₇, x ₈} \ { x ₅, x ₆, x ₇, x ₈} = { x ₁}.

Окрашиваем вершину x ₁ во второй цвет.

Действуя аналогичным образом мы определяем, что вершины x ₂, x ₄ окрашиваются в третий цвет, а вершина x ₃ – в четвёртый.

Таким образом, задача раскраски графа решена, граф раскрашен четырьмя красками.

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

Пример 3. Раскрасить граф из примера 1, через решение задачи покрытия.

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

	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	.
y1	0	0	0	0	1	1	1	1
y2	0	0	0	1	0	1	0	0
y3	0	1	0	0	1	0	0	1
y4	1	0	0	0	0	1	1	1
y5	0	1	0	1	0	0	0	0
y6	0	0	1	1	0	0	0	0

Выбираем первую строку этой таблицы. Она покрывает элементы x ₅, x ₆, x ₇, x ₈. Вторая строка перекрывает вершину x ₄. Третья строка - вершину x ₂. Четвертая - вершину x ₁. И, наконец, шестая - вершину x ₃. Таким образом, мы получили раскраску исходного графа пятью цветами.

1 вариант: 1–я краска – x ₅, x ₆, x ₇, x ₈; 2–я краска – x ₄; 3–я – x ₂; 4–я – x ₁; 5–я – x ₃.

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

2 вариант: 1 – я краска – x ₁, x ₆, x ₇, x ₈ (4–я строка таблицы); 2–я краска – x ₃, x ₄ (6–я строка таблицы); 3–я – x ₂, x ₅ (3–я строка таблицы).

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Что такое число внутренней устойчивости графа?

2. Что такое независимое подмножество вершин графа?

3. Каким образом выделяется независимое подмножество вершин графа?

4. Какое подмножество вершин графа называется предельным?

5. Приведите механизм определения внутренне устойчивых подмножеств.

6. Опишите идею алгоритма выделения независимых подмножеств в графе.

7. Что такое число внешней устойчивости?

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

9. Что такое минимальное внешне устойчивое подмножество?

10. Опишите основную идею алгоритма выделения минимальных внешне устойчивых подмножеств.