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

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

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

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

Пример

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

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