Вычисление чисел внутренней и внешней устойчивости

Внутренне-устойчивое множество вершин – множество вер-
шин графа, никакие две вершины которого не инцидентны. Пустой подграф – внутренне-устойчивое множество вершин,
такое, что: при добавлении к нему хотя бы одной вершины образуется хотя бы одно ребро.
Пустой подграф – максимальное по включению внутреннеустойчивое множество вершин. В данном определении «максимальность» означает «нерасширяемость»; в общем случае граф может иметь несколько пустых подграфов различной мощности.
Вершинное число независимости графа (или число внутрен-
ней устойчивости графа) – мощность наибольшего пустого подграфа, обозначение – ε0(G).
Независимое множество ребер (или паросочетание) – множе-
ство ребер графа, никакие два ребра которого не инцидентны.


Реберное число независимости (или число паросочетания) –
мощность наибольшего паросочетания (независимого множества ребер), обозначение – ε1(G).
В общем случае число вершинной внутренней устойчивости изменяется от n (у пустых графов на n вершинах) до 1 (у полных графов на n вершинах).

Для нахождения числа внутренней устойчивости надо определить мощность максимального пустого подграфа. Существует ал-

горитм поиска пустых подграфов, который позволяет найти все пустые подграфы. Из них выбирается максимальный по мощности.
Пошаговое описание алгоритма:
1)строим фиктивную вершину, ее пометка – множество всех
вершин графа {v1, v2,…,vn} (или ребер – если ищется реберное число внутренней устойчивости, тогда далее во всем алгоритме вместо вершин говорим о ребрах);
2)выбираем любую вершину из указанного в пометке множества, рисуем ее на уровень ниже (это потомок);
3)рядом с ней на этом же уровне рисуем все смежные с ней вершины из множества, указанного в пометке вершины – родителя;
4)в качестве пометки каждой полученной вершины vi указываем множества вершин, входящих в ее неокрестность (т.е. несмежных с vi);
5)повтор шагов 2-4 для всех получающихся веток дерева до тех пор, пока все пометки не будут пустые.