5.3. Маршруты полетов самолетов (1, 55, 64, 65j

Предположим, что вершины неориентированного графа G пред-став.тяют аэропорты, а дуги графа G - этапы полетов (беспосадочные перелеты), которые осуществляются в заданное время. Любой маршрут в этом графе (удовлетворяющий ряду условий, которые могут встретиться на практике) соответствует некоторому реально выполни.мому маршруту полета. Пусть имеется N таких возможных маршрутов и для каждого из них каким-то способом подсчитана его стоимость (например, стоимость /-го маршрута равна cj). Задача нахождения множества маршрутов, имеющего наименьшую суммарную стоимость и такого, что каждый этап полета содержится хотя бы в одном выбранном маршруте, является задачей о наименьшем покрытии с матрицей Т = в которой элемент 1 равен 1, если г-й этап содержится в /-м маршруте, и равен О в противном случае.

Укажем еще на одну разновидность рассмотренной задачи {также часто встречающуюся при назначении маршрутов полетов). Если требовать, чтобы каждый этап содержался только в одном маршруте, то приходим к ЗНР, соответствующей сформулированной выше ЗНП.

5.4. Упрощение логических (булевских) выражений [30, 50, 51, 67, 44, 43]

При упрощении логического выражения (логической формулы) Е, которое, например, задано в дизъюнктивной нормальной форме ), достаточно рассмотреть только множество Р простых импликантов формулы Е. Наипростейшая форма^) для Е получается тогда с помощью выделения в Р подмножества Р наименьшей мощности, удовлетворяющего условию: каждая элементарная конъюнкция К шз Е покрывается по крайней мере одним простым импликантом J из Р (т.е. импликация К J является тождественно истинной). Очевидно, что задача нахождения наипростейшей формы является ЗНП со стоимостями Cj = i для всех J = 1, . . ., N.

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

1) Часто применяют сокращение - д.н.ф.- Прим. ред.

) Наипростейшая форма, рассматриваемая здесь, часто называется кратчайшей д.н.ф. Широко известны и другие д.н.ф.- минимальные, тупиковые, сокращенные.- Прим. ред.

5.5. Задача о развозке (о доставке) [7, 47, 24)

В задаче о развозке граф представляет сеть дорог, одна его вершина представляет склад, а все остальные вершины изображают потребителей. Транспорт, покидающий склад, снабжает товаром некоторых потребителей, после чего возвращается на склад. Пусть стоимость маршрута j равна Cj (например, Cj может быть километражем маршрута или временем, необходимым для его црохождения). Спрашивается, сколько машин следует использовать на разных маршрутах, чтобы в один и тот же день доставлять всем потребителям товары (каждому потребителю поставляется сразу все необходимое) и чтобы суммарная стоимость проходимых маршрутов была наименьшей. Эту задачу, очевидно, можно рассматривать как ЗНР, в которой столбцы представляют всевозможные осуществимые (с учетом практических ограничений) замкнутые маршруты, начинающиеся и кончающиеся на складе. Строки представляют потребителей.

Почти идентична рассмотренной задаче задача о прокладке электрического кабеля для подачи электроэнергии от подстанции (склада) к потребителям в кольцевых схемах энергоснабжения [15]. Другие практические приложения ЗНП и ЗНР связаны с синхронизацией линий сборки [59, 25], государственным районированием [291, с вычислением границ в задачах общего целочисленного программирования [18], с сетевым планированием [20] и с разработкой схем защиты и нападения [8, 10].

5.6. Другие задачи о покрытии графов

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

5.6.1. Наименьшее доминирующее множество. Как упоминалось в разд. 4 настоящей главы, задача о нахождении наименьшего доминирующего множества графа G является ЗНП с такой матрицей Т, которая получается в результате транспонирования матрицы смежности графа G с единичными элементами на главной диагонали.

5.6.2. Наибольшее независимое множество. Один из способов нахождения наибольшего независимого множества вершин графа G = (Z, Г) состоит в построении всех максимальных независимых множеств вершин и выборе из них множества с наибольЩей мощностью. Другой способ таков: исходная задача интерпретируется

5 Н. Кристофидес

как ЗНП, в которой столбцы матрицы Т соответствуют вершинам графа G, а строки - ребрам, причем tij = 1, если вершина Х} инцидентна ребру а^, и = О в противном случае.

Тогда очевидно [23], что если X X - множество столбцов в (наименьшем) решении рассматриваемой ЗНП, то множество X - X является наибольшим независимым множеством графа О. Это справедливо потому, что если X - множество, покрывающее ребра графа О, то каждое ребро инцидентно по крайней мере одной вершине из X и, следовательно, никакие две вершины множества X - X не могут быть смежными, т. е. X - X - независимое множество. Более того, если X - X является независимым, то каждое ребро графа инцидентно самое большее одной вершине из X - X и, значит, X - множество, покрывающее ребра графа G. Отсюда следует, что дополнение каждого множества вершин, покрывающего ребра графа G, является независимым множеством, а поскольку X имеет наименьшую возможную мопщость, то X - X есть наибольшее независимое множество.

5.6.3. Наименьшее покрытие и наибольшее паросочетание (см. гл. 12). То, что в литературе называют наименьшим покрытием , представляет собой множество Е ребер графа G = (X, А), такое, что каждая вершина графа G инцидентна по крайней мере одному ребру из £ и мощность множества Е - минимально возможная. Таким образом, поскольку Е можно рассматривать как доминирующее над вершинами графа G, то множество Е* - наименьшее из таких множеств - можно назвать, согласно терминологии, использованной в этой главе, наименьшим доминирующим множество ребер. Известна иная задача о нахождении наименьшего покрытия: нужно отыскать специальное множество М ребер графа G - в М не должно быть смежных ребер. Множество М называют паросочетанием, а множество М* - с наибольшей мощностью - является наибольшим паросочетанием, его можно называть также наибольшим независимым множеством ребер. Эквивалентность задач о наибольшем паросочетании и о наименьшем покрытии демонстрируется в гл. 12, посвященной изучению паросочетании. Там устанавливается, в частности, следующее утверждение: пусть в наибольшем покрытии Е* степень вершины Xi есть d* (xi) (рассматриваются только ребра из Е*), тогда, если для каждой вершины с d* (xj) >1 удалить d* (xj) - 1 ребер, инцидентных Xj, то оставшееся множество ребер образует наибольшее паросочетание. Обратно, если М* есть наибольшее паросочетание и для каждой вершины Xj с с d* (xt) = О добавляется ребро, инцидентное х,-, то получающееся множество ребер образует наименьшее покрытие.