ОПРЕДЕЛЕНИЕ. Числом внешней устойчивости графа G называется значение минимальной мощности для внешне устойчивых множеств этого графа

Числом внешней устойчивости графа G называется значение минимальной мощности для внешне устойчивых множеств этого графа.

Число внешней устойчивости графа G обозначается как (G).

Пример. Для графа G, изображенного на рис. 5.27., (G)= 3 и (G)= 2.

Рис. 5.27.

В качестве примера использования введенных понятий рассмотрим две задачи:

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

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

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

Тогда первая задача состоит в нахождении значения (G) для графа G, представляющего шахматную доску.

Вторая задача заключается в нахождении значения (G) для того же графа.