Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

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

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

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

ЗНП своим названием обязана следующей теоретико-множественной интерпретации. Даны множество и семейство множеств Любое подсемейство семейства , такое, что

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

т. е. множества попарно не пересекаются, то называется разбиением множества

Если каждому поставлена в соответствие (положительная) стоимость то ЗНП формулируется так: найти покрытие множества имеющее наименьшую стоимость, причем стоимость семейства — определяется как Аналогично формулируется и задача о наименьшем разбиении (ЗНР).

В матричной форме, упомянутой ранее, когда строки -матрицы состоящей из нулей и единиц, покрываются столбцами, ЗНП может быть сформулирована как задача линейного программирования:

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

где

и

Для ЗНР неравенства (3.14) обращаются в равенства

<< Предыдущий параграф Следующий параграф >>
Оглавление