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

4. Задача о назначениях

В этом разделе мы рассмотрим частный случай паросочета-ний — в двудольных графах [9, 18, 25]. Задан двудольный граф где и независимые множества вершин и каждое ребро имеет и вес Мы хотим найти совершенное паросочетание графа с максимальным (или минимальным) весом. Минимизационный вариант этой задачи хорошо известен в литературе как задача о назначениях и он без потери общности часто обсуждается в связи с полными двудольными графами.

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

С другой стороны, ЗН можно рассматривать как частный случай ЗМП и решать ее с помощью специализированной версии алгоритма из разд. 3.1.1. Главная трудность, связанная с этим общим алгоритмом — образование и срезание цветков, — в случае ЗН отсутствует, так как в двудольном графе не может существовать циклов с нечетным числом ребер. Так как обычно принято рассматривать ЗН как задачу минимизации, то мы последуем этому обычаю и опишем минимизационный вариант алгоритма из разд. 3.1.1, применимый только к двудольным графам. Изменения, которые нужно сделать в случае задачи максимизации, тривиальны.

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