[предыдущая тема] [оглавление] [следующая тема]

 

11. Внешне устойчивые множества вершин.

 

- внешне устойчивое множество

- число внешней устойчивости

 

 

Определение 8.2. Пусть G(X,E) – неориентированный граф. Множество вершин YÌX называется внешне устойчивым, если для любой вершины xÏY существует вершина yÎY и ребро eÎE, такие, что e=(x,y). Аналогично, множество вершин YÌX орграфа G(X,Y) называется внешне устойчивым, если для любой вершины xÏY существует вершина yÎY и дуга eÎE, такие, что e=(x,y).

Пусть G(X,E) – произвольный граф, T – множество всех внешне устойчивых множеств графа G. Число

называется числом внешней устойчивости графа G.

 

Метод К.Магу нахождения минимальных

внешне устойчивых множеств

 

Пусть G(X,E) – ориентированный граф без параллельных ребер и Y – некоторое множество вершин этого графа , т. е. YÍX.

Введем булевы переменные Y1, Y2, ... ,Yn, соответствующие вершинам графа G (X,E), а также оценку <e1, e2, ... , en> списка переменных <Y1, Y2, ... ,Yn>.

Отметим, что для всех вершин xi, принадлежащих множеству Y, внешне устойчивых,  можно записать:

                                            (8.5)

где   aij– элемент матрицы смежности  вершин графа.

Условие (8.5) можно записать так:

                                      (8.6)

Обозначив

 в виде

                                                  (8.7)

Таким образом, справедливо следующее утверждение: необходимым и достаточным условием внешней устойчивости множества YÍX является выполнение равенства (8.7).

Из приведенного утверждения следует, что внутренне устойчивые множества вершин графа G и только они соответствуют оценкам списка переменных <Y1, Y2, ... , Yn>, на котором выполняется равенство F=1, что дает простой способ выделения всех внешне устойчивых множеств.

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

Пример 8.2.  Построить множества внешне устойчивых вершин графа, приведенного на рис. 8.1.

Составим логическую функцию F согласно (8.6):

Определяем минимальную ДНФ этой функции:

Выбираем вершины,  вошедшие в состав элементарных конъюнкций:

                  

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

 

[предыдущая тема] [оглавление] [следующая тема]