Определение чисел устойчивости графа

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

Поиск числа внутренней устойчивости по методу Магу сводится к составлению систем логических (булевых) уравнений по матрице смежности графа с последующим ее решением. Результатом решения являются все максимальные внутренне устойчивые множества вершин графа, среди которых и выбирается число внутренней устойчивости. При составлении логических уравнений для каждой i-ой строки для всех клеток матрицы с единицами выписываются выражения вида: ivj, где j - номер столбца, на пересечении которого с i-ой строкой стоит единица, причем, i ¹ j. Затем все полученные выражения объединяются с помощью конъюнкций и выполняются всевозможные упрощения (раскрываются скобки и выполняются поглощения).

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

Пример

Рис.2

Граф задан матрицей смежности (рис.2).

Для него имеем: (2v1)(3v1)(4v2)(3v2)=(23v13v12v1)(43v23v24v2)=

=(23v1)(43v2)=134v234v23v12=134v23v12;

Максимальными внутренне устойчивыми будут множества:{2},{1,4},{3,4}.

Максимальная мощность полученных множеств - 2, следовательно, число внутренней устойчивости тоже равно двум.

Поиск числа внешней устойчивости по методу Магу состоит в составлении для каждого j-го столбца матрицы смежности выражений вида: jvivkvlv...vm, где i,k,l,m - номера строк матрицы смежности, на пересечении которых со столбцом j ставится единица. Подобные выражения записываются для каждого столбца матрицы, затем они объединяются с помощью конъюнкций. После преобразований и упрощений получаются конъюнкции, определяющие устойчивые множества. Для рассмотренного примера (рис.2) имеем:

1v(1v2v3)(2v3v4)(3v3)(4v4)=(1v2v3)(2v3v4).3.4=

(12v2v23v13v3v14v24v34).3.4=3.4(2v3v14)=134v34v234=34.

Т.о., внешне устойчивым является множество {3,4}, а число внешней устойчивости равно двум.

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

В рассмотренном примере ядро графа образуют вершины 3 и 4.