6.6.1. Внутренняя устойчивость

Внутренне-устойчивое множество вершин – множество вер-

шин графа, никакие две вершины которого не инцидентны. Пустой подграф – внутренне-устойчивое множество вершин,

такое, что: при добавлении к нему хотя бы одной вершины образуется хотя бы одно ребро.

Пустой подграф – максимальное по включению внутреннеустойчивое множество вершин. В данном определении «максимальность» означает «нерасширяемость»; в общем случае граф может иметь несколько пустых подграфов различной мощности.

Вершинное число независимости графа (или число внутрен-

ней устойчивости графа) – мощность наибольшего пустого подграфа, обозначение – ε0(G).

Независимое множество ребер (или паросочетание) – множе-

ство ребер графа, никакие два ребра которого не инцидентны.

Реберное число независимости (или число паросочетания) –

мощность наибольшего паросочетания (независимого множества ребер), обозначение – ε1(G).

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