графа, а множество
графа, а множество S*, на котором этот минимум достигается, называется наименьшим доминирующим множеством. Для нашего примера ?[G]=3.
Задача. Пусть город можно изобразить как квадрат, разделенный на 16 районов. Считается, что опорный пункт милиции, расположенный в каком-либо районе, может контролировать не только этот район, но и граничащие с ним районы. Требуется найти наименьшее количество пунктов милиции и места их размещения, такие, чтобы контролировался весь город.
Представим каждый район вершиной графа и ребрами соединим только те вершины, которые соответствуют соседним районам. Нам необходимо найти число доминирования графа и хотя бы одно наименьшее доминирующее множество. Для данной задачи ?[G]=4, и одно из наименьших множеств есть (3, 5, 12, 14). Эти вершины выделены на рисунке.
3.7.4. Задача о наименьшем покрытии
Рассмотрим граф. На рисунке показана его матрица смежности А и транспонированная матрица смежности с единичными диагональными элементами А*. Задача
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
