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

 

Множество внешней устойчивости – множество вершин, для которых выполняется одно из следующих правил:

1). Любая вершина входит в это множество

2) Либо вершина не входит в это множество, но из этой вершины есть дуга в данное множество.

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

(3.12)

Число внешней устойчивости (β) – это наименьшая мощность из всех множеств внешней устойчивости.