Рис. 3.4.

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

Если мы представим каждый район вершиной графа и ребрами соединим только те пары вершин, которые соответствуют соседним районам, то получится граф, показанный на рис. 3.3(6). Тогда задача сводится к определению наименьшего доминирующего множества в этом графе. Число р [G] является наименьшим числом баз, покрывающих всю территорию. Для графа, приведенного на рис. 3.3(6), р [G] = 4 и базы следует размещать в квадратах, номера которых принадлежат множеству {3, 5, 12, 14} или множеству {2, 9, 15, 8}.

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

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

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

Или, в другой терминологии, вес .- Прим. ред.

2) В другой терминологии - покрытие наименьшего веса .- Прим. ред.

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

4. Задача о наименьшем покрытии

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

В общей ЗНП матрица, состоящая из О и 1, не обязательно является квадратной. Кроме того, каждому столбцу j (в нашем случае каждой вершине Xj) сопоставляется некоторая стоимость ) Cj и требуется выбрать покрытие (или, в другой терминологии - для случая графов - доминирующее множество вершин) с наименьшей общей стоимостью ). Поскольку задача построения наименьшего доминирующего множества вершин является весьма частной задачей о покрытии с = 1 для всех 7 = 1, . . ., га, то на первый взгляд кажется, что нахождение такого множества осуществляется на деле значительно проще, чем решение общей ЗНП. Однако это, вообще говоря, не так. Поэтому в данном разделе мы начнем с решения общей ЗНП.

4.1. Постановка задачи

ЗНП своим названием обязана следующей теоретико-множественной интерпретации. Даны множество R = {г^, . . ., Гд} и семейство = {Si, . . ., S) множеств Sj а R. Любое подсемейство аР - {Sj, Sj, . . ., SjJ семейства , такое, что

USj=R, (3.12)

при ограничениях

S tijlj>i, i=l,2, ...,М, (3.14)

где Cj > О,

1, если SjiS \ если Sj

[1, если ViSj, {о, если rtSj. Для ЗНР неравенства (3.14) обращаются в равенства

S tijlji, f = l,2, ...,М. (3.15)

4.2. Упрощение задачи

Вследствие особой природы ЗНП часто удается сделать при ее исследовании определенные, хорошо известные заранее выводы и упрощения [6, 26, 27, 28, 30, 50, 51].

Например:

(1) если для некоторого элемента из R справедливы соотношения ri Sj У] = i, . . ., N, то Tj покрыть нельзя и, следовательно, задача не имеет решения;

называется покрытием множества R, а множества Sj. называются покрывающими множествами. Если в дополнение к соотношению (3.12) of удовлетворяет условию

Sj []Sj==0, yh, к), кф1, (3.13)

т. е. множества Sj. (i = i, ... к) попарно не пересекаются, то <5° называется разбиением множества R.

Если каждому Sj поставлена в соответствие (положительная) стоимость Cj, то ЗНП формулируется так: найти покрытие множества R, имеющее наименьшую стоимость, причем стоимость

семейства <У = {Sj , . . ., Sj } определяется как У] с,-.. Анало-

1 й t l

гично формулируется и задача о наименьшем разбиении (ВНР).

В матричной форме, упомянутой ранее, когда строки (М X Л')-матрицы [tij], состоящей из нулей и единиц, покрываются столбцами, ЗНП может быть сформулирована как задача линейного программирования:

минимизировать z= 2 /1;