Вычисление чисел внутренней и внешней устойчивости

Задача 6.8. Для заданного графа (рис. 6.27) найти все пустые подграфы и число вершинной внутренней устойчивости.

		1		Решение. В соответствии с ал-
				горитмом получим дерево (рис.
	2	3		6.28).
				В этом дереве все пути от фик-
		5		тивной вершины до каждого листа
	4			есть пустые подграфы или макси-
		6		мальные		внутренне		устойчивые
		7		множества (в данном случае –
		вершины). Повторные пути указы-
		ваются	единократно.		Например,

пути 1-4-6, 1-6-4 и 4-1-6 задаются единственный раз множеством
{1,4,6}.
Выбираем из них самое длинное (с максимальной мощностью), это, например, {1,4,6}, его мощность равна 3. Значит, ε0=3.
Пустые подграфы: {2,6}, {2,7}, {1,5,7}, {1,4,6}, {3,2,7}, {3,4}. ε0=3.



{1,2,3,…,7}

{6,7}

2

{4,5,6,7}

1

{2,4,7}

3

{1,7}

5

{1,3,6}

4

6	7	5	4	6	2	4	1	1	3
		{7}	{6}	{4}	{7}		{7}	{6}
		7	6	4	7		7	6

Внешняя устойчивость

Прежде чем определить понятие внешней устойчивости, введем правила покрытия.
Любая вершина покрывает:
саму себя;
смежные вершины;
инцидентные ребра. Любое ребро покрывает:
само себя;
смежные ребра;
инцидентные вершины.
Вершинное число внешней устойчивости – минимальная мощность множества вершин, покрывающих все вершины графа, обозначается 0.
Реберное число внешней устойчивости – минимальная мощ-
ность множества ребер, покрывающих все ребра графа, обозначается 1. В общем случае число вершинной внешней устойчивости изменяется от n (у пустых графов на n вершинах) до 1 (у полных графов на n вершинах).

+

Основная идея алгоритма поиска минимального покрытия
заключается в построении модифицированной матрицы смежности (обычная матрица смежности, только по главной диагонали у нее единички), чтобы затем при помощи алгебры логики найти наименьшее число строк, покрывающих все столбцы этой матрицы (или столбцов, покрывающих строки – разницы нет, матрица симметричная).
Пошаговое описание алгоритма:
1)построить матрицу смежности и заполнить все клетки главной диагонали единичками;
2)составить логическое выражение в виде произведения сумм логических переменных, соответствующих вершинам графа (или ребрам – если ищется реберное число внешней устойчивости). Каждая сумма представляет собой сложение переменных, которые в данной строке содержат «1». Логическое сложение обозначается
как «+», логическое умножение – как « »;
3)привести это выражение к ДНФ (дизъюнктивной нормальной форме), т.е. к сумме произведений переменных;
4)мощность максимального слагаемого и есть искомое число внешней устойчивости.
Задача 6.9. Для заданного графа с достаточным обоснованием найти число внешней вершинной устойчивости.


Решение. Получим матрицу:

				1			2			3			4			5			6
	1			1			1			1
	2			1			1			1			1			1
	3			1			1			1						1			1
	4						1						1			1
	5						1			1			1			1			1
	6									1						1			1

Из нее получаем логическое выражение (идем по строчкам):
Покрытие = (1+2+3) · (1+2+3+4+5) · (1+2+3+5+6) · (2+4+5) × × (2+3+4+5+6) · (3+5+6).
Упрощаем с учетом того, что по закону поглощения: (1+2+3) · (1+2+3+4+5) = (1+2+3), (2+4+5) · (2+3+4+5+6) = (2+4+5), (1+2+3+5+6) · (3+5+6) = (3+5+6).
Покрытие = (1+2+3) · (2+4+5) · (3+5+6).
Раскрываем скобки с учетом того, что
(2+4+5) · (3+5+6)=5+2·3+2·6+4·3+4·6. Покрытие = (1+2+3) · (5+2·3+2·6+4·3+4·6) =
=1·5+1·2·3+1·2·6+1·4·3+1·4·6+2·5+2·2·3+2·2·6+2·4·3+2·4·6+3·5+
+3·2·3+3·2·6+3·4·3+3·4·6.
Упрощаем по закону поглощения (x+x·y=x) и с учетом x·х=x.
Покрытие = 1·5+1·2·3+1·2·6+1·4·3+1·4·6+2·5+2·2·3+2·2·6+
+2·4·3+2·4·6+3·5+3·2·3+3·2·6+3·4·3+3·4·6 =
=2·6+2·3+2·3+4·3+1·5+1·4·6+2·5+3·5 = =
2·6+2·3+4·3+1·5+1·4·6+2·5+3·5.
Получили ДНФ, выбираем самое короткое слагаемое, например 2·6. Значит, искомое число внешней устойчивости равно 2, а пример внешне устойчивого множества вершин – {2,6}.


Ответ: β0.=2.
Дадим определения сразу для неориентированного и ориентированного случаев, учиты-вая, что эти определения очень похожи (отличия будем указывать в скобках). Две различные вершины, которые соединены ребром (дугой), т.е. являющиеся концами одного и того же ребра (дуги), называются смежными. В противном случае две вершины не смежны. Множество X вершин графа G, любые две из которых не смежны, называется внутренне устойчивым, а мак- симально возможное число элементов внутренне устойчивого множества − числом внутренней устойчивости графа G (обозначается α(G)).
Сразу поясним это не очень простое понятие. Прежде всего, любое множество вершин, со-стоящее из одной вершины, является по определению внутренне устойчивым как в неориенти-рованном, так и в ориентированном случае. Действительно, определение внутренней устойчи-вости множества вершин X, как и почти все математические определения, является импликаци-ей. Его можно переформулировать так: «Если любые две разные вершины множества X не смежны, то множество X называется внутренне устойчивым» или, пользуясь определёнными в главе 1-4 кванторами, короче
(  aÎX)(  bÎX)[(a ≠b)→(a не смежна с b)]. (3)
Но если множество X состоит из одной вершины, то посылка a ≠b импликации всегда ложна, поскольку a и b – две разные вершины из множества X. Напомним, что по определению импли-кации), импликация с ложной посылкой всегда истинна «в силу ложности посылки». Но это и означает истиннось импликации , что и означает внутреннюю устойчи-вость любого одноэлемнтного множества.
Утверждение 1. Любое подмножество внутренне устойчивого множества внутренне ус-тойчиво
Действительно, по определению, во внутренне устойчивом множестве никакие две верши-ны не соединены ребром. Значит, этим же свойством обладает и любое его подмножество ■
Внутренне устойчивое множество вершин называется максимальным по включению, ес-ли оно не содержится ни в каком другом внутренне устойчивом множестве. Утверждение 1 позволяет при поиске всех внутренне устойчивых множеств ограничиться поиском только максимальных по включению внутренне устойчивых множеств. Действительно, всякое внут-ренне устойчивое множество либо само является максимальным по включению, либо содержит-ся в некотором максимальном по включению внутренне устойчивом множестве. (Заметим, что таких множеств может быть несколько). Поэтому семейство всех максимальных по включению внутренне устойчивых множеств определяет все внутренне устойчивые множества: множество является внутренне устойчивым, если оно содержится хотя бы в одном максимальном по вклю-чению внутренне устойчивом множестве.
В произвольном графе с небольшим числом вершин максимальные по включению внут-ренне устойчивые множества могут быть найдены простым перебором всех различных подмно-жеств, начиная с множества всех вершин. Однако самый простой и эффективный подход – вни-мательно посмотреть на граф собственными глазами (и подумать собственной головой). Конеч-но, в графах, содержащих порядка 15 и более вершин, такой просмотр практически нереален. Формальные алгоритмы решения данной задачи в силу своей сложности здесь не рассматрива-ются.
Введём дальнейшие понятия. Множество X вершин графа G называется внешне устойчи-вым, если любая вершина из V  X, т.е. вершина, не принадлежащая X, смежна хотя бы с одной вершиной из X (является концом некоторой дуги, начало которой принадлежит множеству вер-шин X, в ориентированном случае). Минимально возможное число элементов внешне устойчи-вого множества называется числом внешней устойчивости графа G (обозначается β(G)). Об-ратим внимание на то, что связность вершин внутри множества X не оказывает никакого влия-ния на данное свойство. Это значит, что добавление или удаление любого ребра (дуги) между вершинами из X не повлияет ни на наличие свойства внешней устойчивости у множества X, ни на его отсутствие. Обратим внимание, что в определении не требуется, чтобы какая-нибудь вер-шина из X была бы смежной со всеми вершинами из V  X. Достаточно, если любая вершина из V  X смежна хотя бы с какой-нибудь вершиной из X. Для разных «внешних» вершин (т.е. из V  X) смежные с ними «внутренние» вершины (т.е. из X) могут (но не обязаны!) быть различны-ми.
Заметим, что само множество всех вершин V является внешне устойчивым в силу ложнос-ти посылки. Действительно, при X = V имеем V  X = Æ, т.е. вершин, не принадлежащих X, прос-то не существует. Как и определение внутренне устойчивого множества, определение внешне устойчивого множества является импликацией:
(  aÎV  X)→(  bÎX)(a смежна с b), (4)
которая всегда верна при ложной посылке (  aÎV  X).
Имеет место простое
Утверждение 2. Любое множество, содержащее внешне устойчивое множества вершин, также внешне устойчиво.
Действительно, пусть внешне устойчивое множество XÍY. Для всякой вершины zÎV  Y верно zÎV  X. Так как X – внешне устойчивое множество, то, по определению, z смежна с неко-торой вершиной wÎX (является концом дуги с началом w). А в силу включения XÍY имеем wÎY. Таким образом, начав с произвольной вершины zÎV  Y, установили, что она смежна с некоторой вершиной wÎY (является концом дуги с началом w), что, по определению, означает внешнюю устойчивость Y ■
Внешне устойчивое множество называется минимальным по включению, если оно не содержит ни одного другого внешне устойчивого множества. В силу утверждения 2, для нахож-дения всех внешне устойчивых множеств достаточно найти только минимальные внешне ус-тойчивые множества. Все остальные являются произвольными множествами, содержащими хо-тя бы одно минимальное по включению внешне устойчивое множество.
Проиллюстрируем теперь это понятие на том же графе
Пример 8. На рис.6а – 6е показаны все минимальные по включению внешне устойчивые множества в данном графе. На каждом из этих рисунков видно, что любая вершина, показанная чёрным кружком (как в исходном графе) соединена хотя бы с одной вершиной из внешне ус-тойчивого множества, выделенных квадратами. Ясно также, что при удалении любой вершины из внешне устойчивого множества все эти множества перестают быть внешне устойчивыми – появляются вершины, не соединённые ни с одной из оставшихся вершин. Обратим внимание на то, что минимальные по включению внешне устойчивые множества могут содержать различное число вершин – две на рис.6а – 6в и три на рис.6г – 6е.
Множество, показанное на рис.6ж, является внешне устойчивым, но не минимальным по включению. Оно содержит множества, показанные на рис.6б и 6в. Наконец, множество, пока-занное на рис.6з, не является внешне устойчивым. Вершина 3 не соединена ребром ни с верши-ной 1, ни с вершиной 4, что противоречит определению внешне устойчивого множества.
Поскольку минимальное число вершин во внешне устойчивом множестве равно 2, то чис-ло внешней устойчивости β(G) = 2.

Видно непосредственно на рисунке, что любое множество, содержащее одну вершину, не будет внешне устойчивым – просто потому, что в исходном графе нет ни одной вершины, со-единённой со всеми остальными ■ Как и для внутренне устойчивых множеств, формальные алгоритмы решения данной зада-чи в силу своей сложности здесь не рассматриваются. Множество X вершин графа G, одновременно внутренне и внешне устойчивое, называет-ся ядром графа G. Напомним, что определения внутренне устойчивого множества вершин в неориентрован-ном и ориентированном случаях совпадают. Совпадают и определения ядра. Отличаются толь-ко определения внешне устойчивого множества: в ориентированном случае требуется, чтобы дуга, соединяющая множества X и V  X, имела направление от X к V  X. Из определений внутренней и внешней устойчивости непосредственно следует, что: - любая изолированная вершина графа может быть добавлена к любому не содержащему её внутренне устойчивому множеству и это расширенное множество также будет внутренне устойчивым; - любое внешне устойчивое множество обязано содержать любую изолированную верши-ну. Из утверждений 1 и 2 непосредственно следует Утверждение 3.Множество вершин Z является ядром графа G тогда и только тогда, когда существуют минимальное по включению внешне устойчивое множество X и максимальное по включению внутренне устойчивое множество Y, такие, что X  Z  Y. (5)■ Множество ТМX называется внешне устойчивым в графе (Х,Г), если для каждой вершины хПТ существует хотя бы один образ во множестве Т. Числоb(G) =   называется числом внешней устойчивости. Прежде чем определить понятие внешней устойчивости(external stability ), введем правила покрытия графа. Любая вершина покрывает: саму себя; смежные вершины; инцидентные ребра. Любое ребро покрывает: само себя; смежные ребра; инцидентные вершины. Вершинное число внешней устойчивости – минимальная мощность множества вершин, покрывающих все вершины графа, обозначается 0. Реберное число внешней устойчивости – минимальная мощность множества ребер, покрывающих все ребра графа, обозначается 1. В общем случае число вершинной внешней устойчивости изменяется от n (у пустых графов на n вершинах) до 1 (у полных графов на n вершинах). Основная идея алгоритма поиска минимального покрытия заключается в построении модифицированной матрицы смежности (обычная матрица смежности, только по главной диагонали у нее единички), чтобы затем при помощи алгебры логики найти наименьшее число строк, покрывающих все столбцы этой матрицы (или столбцов, покрывающих строки – разницы нет, матрица симметричная). Примеры: сколько можно поставить ферзей (рис.12) или других фигур, чтобы все поля доски были под ударом (5 ферзей, 8 ладей или слонов, 12 коней), сколько наблюдателей поставить на пересечениях улиц, чтобы все перекрестки были под присмотром. Существует достаточно простой алгоритм поиска минимального внешне устойчивого множества . Об этом говорит сайт https://intellect.icu . Для графа G=(X,Г) (см. рис.13a) строим граф (X,  ,D), где определено отображение D множества X в  так, что  , если у=x или y является прообразом х (уОГ^-1х) (рис.13b). Дальнейшие действия: удаляем из (X,  , D) вершины х такие, что Dх М Dу для у№х (здесь мы удаляем c,d,f) и исходящие из них ребра; если обнаружится "висячее ребро" (х,  ), включаем х в искомое множество Т и удаляем эту вершину и ее образы (здесь а ОТ и из графа исключаетсяа и Dа={ }; Рис. 13 повторяем предшествующие пункты до тех пор, пока не обнаружится невозможность дальнейшего приведения; одну из оставшихся вершин (например, b) включаем во множество Т и исключаем ее образы Db={ }; повторяем предшествующие пункты и получаем либо Т=(a,b,e) или Т=(a,b,g). Пусть  - некоторый граф. Подмножество вершин  называется множеством внешней устойчивости, если 1)  2)  Мощность минимального множества внешней устойчивости называется числом внешней устойчивости графа  . Для того, чтобы найти все множества внешней устойчивости графа, надо найти все покрытия модифицированной матрицы смежности графа. Модификация заключается в добавлении единичной главной диагонали. Множества внешней устойчивости: