3. Доминирующие множества

Для графа доминирующее множество вершин (называемое также внешне устойчивым множеством [11]) есть множество вершин выбранное так, что для каждой вершины не входящей в существует дуга, идущая из некоторой вершины множества в вершину

Таким образом, есть доминирующее множество вершин (или просто доминирующее множество, когда нет опасности возникновения путаницы), если

Для графа, приведенного на рис. 3.2, множества вершин являются доминирующими множествами.

Доминирующее множество называется минимальным, если нет другого доминирующего множества, содержащегося в нем.

Рис. 3.2.

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

Если семейство всех минимальных доминирующих множеств графа, то число

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

Для графа, приведенного на рис. 3.2, наименьшим доминирующим множеством является множество следовательно,

3.1. Пример. Размещение «центров», покрывающих заданную область

Задач такого типа весьма много. К ним относятся:

(а) Размещение телевизионных или радиопередающих станций на некоторой территории.

(б) Размещение военных баз, контролирующих данную территорию.

(в) Размещение центров торговли, обслуживающих некоторый район.

Предположим, что территория, представленная большим квадратом на рис. 3.3(a), разделена на 16 районов, как показано на рисунке.

Рис. 3.3.

Предполагается, что военная база, расположенная в каком-либо районе, может контролировать не только этот район, но и соседние, граничащие с ним районы. Требуется найти

Рис. 3.4.

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

Если мы представим каждый район вершиной графа и ребрами соединим только те пары вершин, которые соответствуют соседним районам, то получится граф, показанный на рис. Тогда задача сводится к определению наименьшего доминирующего множества в этом графе. Число является наименьшим числом баз, «покрывающих» всю территорию. Для графа, приведенного на рис. и базы следует размещать в квадратах, номера которых принадлежат множеству или множеству

Аналогично, для территории, показанной на рис. 3.4, число доминирования соответствующего графа равно 12 и базы следует размещать в районах 2, 6, И, 15, 21, 24, 26, 29, 35, 39, 44, 48. Только три заштрихованных квадрата «защищены» одновременно тремя базами.

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

Для случая максимальных независимых множеств мы привели алгоритм, который выдает полный список всех таких множеств.

Сделано это было потому, что такие списки нужны во многих практических задачах [36, 3, 2]. Для доминирующих множеств, однако, требуется обычно найти просто наименьшее доминирующее множество, и поэтому мы ограничимся здесь описанием алгоритма построения такого множества. В следующем разделе мы рассмотрим задачу о нахождении наименьшего доминирующего множества с несколько более общих позиций; это поможет нам глубже разобраться в взаимосвязях между понятиями, рассматриваемыми в других частях книги.