Глава 7 Нахождение потока в сети

В этой главе мы займемся семейством алгоритмических задач, которые в каком- то смысле происходят от одной из исходных задач, сформулированных в начале курса: двудольных паросочетаний.

Вспомните исходную формулировку задачи двудольных паросочетаний.

Дву- дольным графом G = (V, E) называется ненаправленный граф, множество узлов ко- торого может быть разбито на подмножества V = X U Y, обладающее тем свойством, что один конец каждого ребра принадлежит X, а другой конец принадлежит Y. Двудольные графы часто изображаются так, как показано на рис. 7.1: узлы X вы- страиваются в столбец слева, узлы Y — в столбец справа, а ребра переходят между левым и правым столбцом.

Рис. 7.1. Двудольный граф


Концепция паросочетаний уже неоднократно встречалась в этом учебном курсе: этим термином обозначаются совокупности пар в множествах, в которых ни один элемент множества не входит более чем в одну пару. (Вспомните мужчин и женщин из задачи устойчивых паросочетаний или символы из задачи выравнивания после- довательностей.) В случае графа ребра образуют пары узлов, а мы соответственно говорим, что паросочетание в графе G = (V, E) представляет собой множество реберM !Ξ E с тем свойством, что каждый узел присутствует не более чем в одном ребре M. Множество ребер M является идеальным паросочетанием, если каждый узел присутствует ровно в одном ребре M.

Паросочетания в двудольных графах используются для моделирования си- туаций, в которых одни объекты назначаются другим объектам. Вы уже видели примеры таких ситуаций в предшествующих обсуждениях графов и двудольных графов. В одном из естественных такого рода узлы X представляют задания, узлы Y представляют машины, а ребро (x, у) означает, что машина у.

способна обработать задание x.. В этом случае идеальное паросочетание определяет способ распределения заданий между машинами, способными их обработать, при котором каждой машине назначается ровно одно задание. Двудольные графы также могут использоваться для представления других отношений, возникающих между двумя разными множествами объектов: отношений между покупателями и магазинами; домами и обслуживающими их почтовыми отделениями; и т. д.

Задача нахождения наибольшего паросочетания в двудольном графе G относит- ся к числу старейших задач комбинаторных алгоритмов. (Следует заметить, что граф G имеет идеальное паросочетание в том и только в том случае, если X = |Y|, и в нем существует паросочетание размера |X|.) Как выясняется, эта задача решается алгоритмом с полиномиальным временем, но разработка такого алгоритма требует применения идей, принципиально отличающихся от приемов, рассматривавшихся нами ранее.

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

7.1.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Глава 7 Нахождение потока в сети:

  1. Глава 3. ОТКРОЙТЕ СВОЙ ПОТОК ОБРАЗОВ
  2. коян: Восходящий узел - включение в общий поток; Нисходящий узел - исключение из общего потока.
  3. ОБЪЕКТ СЕКСУАЛЬНЫЙ: НАХОЖДЕНИЕ: ПУТЬ
  4. Нахождение аспектов
  5. Нахождение Плутона
  6. Нахождение куспидов домов
  7. Упражнение НАХОЖДЕНИЕ АНАЛОГИЧНОГО ПРЕДМЕТА ДОМА
  8. 3.5. Подключение к сети
  9. Альбатрос (восхождение на поток)
  10. ТЕОРИЯ ПОТОКА СОЗНАНИЯ
  11. 3.9. ПОТОК СОЗНАНИЯ