21.2.4 Внутренняя устойчивость графа

Множество вершин графа, среди которых нет смежных, называется независимым множеством вершин (НМВ) или внутренне устойчивым множеством вершин.

Если такое множество не является подмножеством другого множества с таким свойством, то оно максимально.

Мощность максимального независимого множества вершин (МНМВ) α(G) – называется числом внутренней устойчивости графа.

С помощью приведенного ниже алгоритма можно выделить семейство всех независимых множеств вершин произвольного графа.

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

1. Составить матрицу смежности графа.

2. Обозначить вершины графа логическими переменными, например, x₁,x₂,x₃,…,x_n, гдеx_i= 0, если вершина принадлежит какому либо внутренне устойчивому множеству, иx_i= 1 в противном случае.

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

3. В матрице смежности выбрать строку с максимальным числом ненулевых элементов. Если таких строк несколько, то берется любая из них.

4. Для выбранной строки записывается выражение

где x_i– вершина, соответствующая выбранной строке,x_k,x_l,…,x_q– вершины, смежные ей.

Трактовать это выражение можно так – во внутренне устойчивое множество вершин графа не должна входить вершина x_i или ни одна из вершин, смежных с ней.

5. После этого в строке и столбце матрицы смежности с индексом iединицы заменить нулями (строку и столбец с индексомiможно удалить).

6. В полученной матрице смежности снова выбрать строку с наибольшим числом ненулевых элементов (например, строку j) и записать выражение

7. Строка и столбец с индексом j обнуляются.

8. Процесс повторяется, пока все строки матрицы смежности не станут пустыми (одни нули).

В строках изолированных и тупиковых вершин первоначальной матрицы смежности стоят только 0, поэтому для них не будут составлены выражения C_i. Изолированные вершины обязательно войдут в любое из внутренне устойчивых множеств и будут учтены в п. 10 алгоритма.поэтому их можно сразу исключить из матрицы смежности, упростив тем самым решение задачи. Тупиковые вершины будут учтены в выражениях для вершин, смежных с ними.

9. Из полученных выражений C_i,C_j, ,C_kсоставить произведение

П = C_i C_j …C_k,

в котором надо раскрыть скобки и провести минимизацию.

10. После минимизации для каждой конъюнкции найти не вошедшие в нее вершины графа, которые и образуют независимое множество.

В совокупности получим семейство из всех независимых множеств.

11. Число внутренней устойчивости графа α(G) будет равно количеству вершин, вошедших в максимальное независимое множество вершин.

Пример. Дан графG(6,6) рис. 21.2.

Определить внутренне устойчивые множества графа.

Составляем матрицу смежности графаА

Рисунок 21.2

Выбираем строку 2. Записываем

Обнуляем строку и столбец с индексом 2.

Получим

Выбираем строку 4. Записываем

Преобразуем матрицу

Выбираем строку 1. Записываем

Преобразуем матрицу

Преобразование матрицы закончено – во всех строках и столбцах только нули.

Формируем произведение

П = С₁С₂С₄ =.

После раскрытия скобок и минимизации получаем

П = .

Обозначим

П = K₁K₂K₃K₄.

Дополняющие множества вершин ,,,образуют семейство независимых множеств

=,=,=,={.

Число внутренней устойчивости графа α(G) = 3.