4. Задача о назначениях
В этом разделе мы рассмотрим частный случай паросочета-ний — в двудольных графах [9, 18, 25]. Задан двудольный граф 
где и 
независимые множества вершин и каждое ребро 
имеет 
и вес 
Мы хотим найти совершенное паросочетание графа 
с максимальным (или минимальным) весом. Минимизационный вариант этой задачи хорошо известен в литературе как задача о назначениях 
и он без потери общности часто обсуждается в связи с полными двудольными графами.
Пусть 
Рассматривая полный двудольный граф 
легко видеть, что задача о паросочетании для этого специального случая может быть решена с помощью методов, предназначенных для исследования потоков в сетях (из гл. 11), и поэтому нет необходимости в применении общего алгоритма паросочетания, изложенного в разд. 3 настоящей главы. Пусть добавлен искусственный источник 
с дугами 
имеющими единичную пропускную способность и нулевую стоимость (вес), и искусственный сток 
с дугами 
также имеющими единичную пропускную способность и нулевую стоимость (вес). Если рассматривать ребра из А как ориентированные, т. е. как дуги 
с единичными пропускными способностями, то максимальный поток с минимальной стоимостью (весом) от 
будет иметь значение 
а по этим дугам будет «проходить» ненулевой поток 
значением 1) с минимальной суммарной стоимостью (весом). Эти дуги из А будут тогда образовывать в 
совершенное паросочетание с минимальной стоимостью (весом). Очевидно, что в случае такой специальной структуры графа многие шаги общего алгоритма нахождения потока минимальной стоимости (веса) могут быть упрощены с целью получения более эффективной процедуры для ЗН.
С другой стороны, ЗН можно рассматривать как частный случай ЗМП и решать ее с помощью специализированной версии алгоритма из разд. 3.1.1. Главная трудность, связанная с этим общим алгоритмом — образование и срезание цветков, — в случае ЗН отсутствует, так как в двудольном графе не может существовать циклов с нечетным числом ребер. Так как обычно принято рассматривать ЗН как задачу минимизации, то мы последуем этому обычаю и опишем минимизационный вариант алгоритма из разд. 3.1.1, применимый только к двудольным графам. Изменения, которые нужно сделать в случае задачи максимизации, тривиальны.
