Множество внутренней устойчивости графа

Множество внутренней устойчивости графа – это множество несмежных вершин.

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

(3.4)

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

ПРИМЕР

Дан граф

Рис. 3.6 Граф

Данный граф имеет следующие множества внутренней устойчивости.

Рассмотрим множество . Добавляя к нему любую вершину, получаем множества внутренне неустойчивые: . Следовательно, множество является максимальным множеством внутренней устойчивости.

Числом внутренней устойчивости (α) называется число, равное наибольшей мощности максимального внутренне устойчивого множества.

Очевидно, что поиск максимальных внутренне устойчивых множеств путем простого перебора является неэффективной процедурой, поэтому для поиска максимальных внутренне устойчивых множеств существует специальный алгоритм – алгоритм Магу.