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

Каждой вершине орграфа D=(V,X) поставим в соответствие некоторую булеву переменную y_i следующим образом: если вершина v_i  U, то y_i положим равным 1. Определение внешне устойчивого множества можно записать так: для любой вершины v_i из множества V выполняется одно из условий:

1. вершина v_i  U;

2. вершина v_i  U , тогда существует вершина v_j (j=1n), что v_jU и v_jГv_i.

Запишем это условие в виде формулы алгебры логики, т.е.

y_i (y_j&a_ij)  1.

Рассмотрим конъюнкцию по всем вершинам:

F= ( y_i (y_j&a_ij))  1 или

F= ( y_i y_j)  1.

Учитывая, что ААВ  А и А(АВ)  А, приведем формулу F к ДНФ. Тогда каждый дизъюнктивный член даст минимальное внешне устойчивое подмножество. Действительно, такой член не содержит переменных с отрицанием и поэтому из множества вершин V_i, соответствующих переменным y_i, встречающихся в этом члене, нельзя удалить ни одну.

Пример.

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

Решение.

Запишем формулу F. Имеем

F = (y₁  y₂  y₃  y₅ )( y₂  y₃)( y₃  y₄) y₄ (y₅  y₄)  1.

Упростим формулу, пользуясь формулами поглощения

F = ( y₂  y₃) y₄  1 или F = y₂ y₄  y₃y₄  1.

Итак, имеем два минимальных внешне устойчивых множества: {v₂,v₄ }, {v₃,v₄}.

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

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

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

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

4. Покрытия

Введем еще одно понятие, связанное с понятием внутренне устойчивого множества.

Будем говорить, что вершина v и ребро x графа покрывают друг друга, если они инцидентны. Таким образом, ребро x={v,w} покрывает вершины v и w, а каждая из этих вершин покрывает ребро x.

Подмножество вершин UV называется покрытием (вершинным покрытием, опорой) графа G, если каждое ребро из X инцидентно хотя бы одной вершине из U.

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

Число вершин в наименьшем покрытии графа G называется числом покрытия ( или числом вершинного покрытия) графа G и обозначается через ₀(G).

2

1 3 7

5 4 6

8

Рис. 1.

Например, для графа, изображенного на рис.1, каждое из множеств U₁={4,5,6,8}, U₂={4,5,6,7}, U₃={1,2,3,5,6,8} является покрытием, причем U₁ и U₂ – наименьшие покрытия, а U₃ – минимальное покрытие.

Между покрытиями и независимыми множествами в графе существует тесная связь, а именно, множество вершин U графа G является (наименьшим, минимальным) покрытием тогда и только тогда, когда U^*= V \U – (наибольшее, максимальное) независимое множество.