Внешняя устойчивость орграфа

есть множество положительной внешней устойчивости орграфа , если 1) 2) . Число положительной внешней устойчивости орграфа – мощность минимального множества положительной внешней устойчивости .

есть множество отрицательной внешней устойчивости орграфа , если 1) 2) . Число отрицательной внешней устойчивости орграфа – мощность минимального множества отрицательной внешней устойчивости .

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

Пример

	1	1		1		1
		1	1
			1			1
			1	1	1
					1
					1	1

Множества положительной внешней устойчивости:

Множества отрицательной внешней устойчивости:

Внутренняя устойчивость графа

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

Пример

- не является внутренне устойчивым - является внутренне устойчивым (но не является пустым подграфом) - является внутренне устойчивым (и является пустым подграфом)

Мощность максимального пустого подграфа называется числом внутренней устойчивости графа .

Пусть - некоторый граф, - некоторая вершина, - окрестность вершины . Неокрестность (коокрестность) вершины графа обозначим - подграф графа , порожденный .

Теорема Пустой подграф, содержащий вершину содержит по крайней мере одну вершину из коокрестности вершины .