ОПРЕДЕЛЕНИЕ. Множество I вершин графа G= (V, U) называется внешне устойчивым, если для любой вершиныa V \ Iнайдется такая вершина b

Множество I вершин графа G = (V, U) называется внешне устойчивым, если для любой вершины a V \ I найдется такая вершина b I, что (a, b) U.

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

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

В качестве примера рассмотрим граф, изображенный на
рис. 5.26. a b c

G e

f

d

Рис. 5.26

В этом графе можества:

I = {a, d, c} - внутренне устойчивое;

E = {d, e, c, f, g} - внешне устойчивое;

K = {g, b, e} является одновременно как внутренне, так и внешне устойчивым.

Нетрудно видеть, что удаление элементов внутренне устойчивого множества вершин графа приводит к внутренне устойчивому множеству вершин. Добавление новых вершин к внешне устойчивому множеству вершин графа приводит к внешне устойчивому множеству вершин.