§ 30. Внутренняя устойчивость. Внешняя устойчивость

Внутренне устойчивое подмножество. Пусть задан граф ; подмножество называется внутренне устойчивым, если

Другими словами, никакие две вершины не смежны. Если то также внутренне устойчивое подмножество. Пример. Рассмотрим граф на рис. 120. Подмножества

внутренне устойчивые. Проверим это, например, для

Максимальное внутренне устойчивое подмножество. Это — внутренне устойчивое подмножество, не являющееся собственным подмножеством никакого другого внутренне устойчивого подмножества.

Например (рис. 121 и 122), подмножества максимальные внутренне устойчивые. Очевидно, что граф может обладать несколькими максимальными внутренне устойчивыми подмножествами.

Рис. 120.

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

где — семейство максимальных внутренне устойчивых подмножеств графа Например, для графа на рис. 120

Отыскание семейства максимальных внутренне устойчивых подмножеств (метод Магу). Этот метод использует свойства булевых уравнений.

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

Пусть некоторое внутренне устойчивое подмножество. Свяжем с любой вершиной графа булеву переменную и положим:

Для любой пары вершин (с учетом (30.1)) справедливо утверждение

Рис. 121.

Рис. 122.

Это можно записать так:

или

Беря произведение по всем вершинам графа, получаем уравнение

Учитывая, что упростим эту формулу:

или

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

Пример. Рассмотрим булеву матрицу (рис. 123) графа на рис. 120. Найдем

Рис. 123.

Подставим в (30.10):

Упрощая, получаем

или

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

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

любая вершина не принадлежащая связана по крайней мере с одной вершиной из дугой, начало которой лежит в Можно записать (30.17) также в следующем виде:

Пример (рис. 124). Подмножество внешне устойчивое, что легко проверяется с помощью (30.17):

или с помощью (30.18):

Очевидно, что если то внешне устойчивое подмножество; и любая висячая вершина принадлежит каждому внешне устойчивому подмножеству.

Рис. 124

Рис. 125.

Минимальное внешне устойчивое подмножество. Это — внешне устойчивое подмножество, не содержащее строго никакого другого внешне устойчивого подмножества.

Например, для графа на рис. 125 подмножество внешне устойчивое и минимальное. Граф может обладать несколькими минимальными внешне устойчивыми подмножествами.

Число внешней устойчивости. Это число вершин наименьшего из внешне устойчивых подмножеств. Оно определяется так:

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

Отыскание семейства минимальных внешне устойчивых подмножеств (метод Магу). Из условия (30.18) следует, что такое подмножество должно содержать вместе с по крайней мере одну из вершин Следовательно, справедливо условие

Полагая если определено выше), имеем

Так как

Учитывая, что разложим (30.25). Каждый член этого разложения дает минимальное внешне устойчивое подмножество. Действительно, такой член не содержит переменных с отрицанием, и поэтому из множества вершин соответствующим переменным встречающихся в этом члене, нельзя удалить ни одну.

Пример (рис. 120 и 123). Так как

то в силу (30.25)

Упрощая, имеем

или

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)