Примечания и дополнительная литература

Концепция сетевых потоков впервые была сформулирована в целостном виде в работе Форда и Фалкерсона (Ford, Fulkerson, 1962). Сейчас сетевые потоки ста- ли самостоятельной областью исследований, по которой можно легко прочитать отдельный учебный курс; например, дополнительную информацию можно найти в обзоре Голдберга, Тардоса и Тарьяна (Goldberg, Tardos, Tarjan, 1990) и книге Ахуджа, Маньянти и Орлина (Ahuja, Magnanti, Orlin, 1993).

Шрайвер (Schrijver, 2002) предоставляет интересную историческую информа- цию о начальной стадии работы Форда и Фалкерсона над задачей потока. Те из нас, кому всегда казалось, что в задаче минимального разреза присутствует некий деструктивный оттенок, найдут в этой работе подтверждение своей позиции: в ней цитируется недавно рассекреченный отчет ВВС США, из которого следует, что изначально задача нахождения минимального разреза формулировалась для же- лезнодорожной сети Советского Союза, а целью была дезорганизация перевозок.

Как упоминается в тексте, задачи о двудольном паросочетании и непересека- ющихся путях были сформулированы за несколько десятилетий до задачи о мак- симальном потоке; только разработка теории сетевых потоков поставила все эти задачи на общую методологическую основу. У теории паросочетаний в двудольных графах было много независимых первооткрывателей; вероятно, чаще других упо- минаются П. Холл (Hall, 1935) и Кёниг (Kоnig, 1916). Задача нахождения путей, непересекающихся по ребрам, от источника к стоку, эквивалентна задаче о макси- мальном потоке с пропускными способностями, равных 1; этот частный случай был разрешен (фактически в эквивалентной форме) Менгером (Menger, 1927).

Алгоритм проталкивания предпотока был разработан Голдбергом (Goldberg, 1986), а его эффективная реализация разработана Голдбергом и Тарьяном (Goldberg, Tarjan, 1986). Высокопроизводительный код для этого и других алго- ритмов сетевого потока можно найти на сайте Эндрю Голдберга.

Алгоритм сегментации изображений с использованием минимальных разрезов был разработан Грейгом, Портеусом и Сехолтом (Greig, Porteous, Seheult, 1989), а применение минимальных разрезов стало играть активную роль в области об- работки изображений (например, см.

Векслер (Veksler, 1999), Колмогоров и Забих

Примечания и дополнительная литература 457

(Kolmogorov, Zahir, 2004)); расширения этого подхода обсуждаются в главе 12. Уэйн (Wayne, 2001) приводит дополнительную информацию о выбывании бейсбольных команд, а также приписывает популяризацию этой задачи в 1960-х годах Алану Хоффману. Другие практические применения сетевых потоков и разрезов рас- сматриваются в книге Ахуджа, Маньянти и Орлина (Ahuja, Magnati, Orlin, 1993).

Задача нахождения идеального паросочетания с минимальной стоимостью является частным случаем задачи о потоке с минимальной стоимостью, выходя- щей за рамки материала. Существует несколько эквивалентных формулировок задачи о потоке с минимальной стоимостью; в одной из формулировок дается по- токовая сеть с пропускными способностями cг и стоимостями Ce ребер; стоимость потока∕равна сумме стоимостей ребер, взвешенной по величине передаваемого по ним потока, , а целью является построение максимального потока

с минимальной общей стоимостью. Задача нахождения потока с минимальной стоимостью решается за полиномиальное время, и тоже имеет множество практи- ческих применений; алгоритмы для этой задачи обсуждаются в книгах Кука и др. (Cook et al., 1998) и Ахуджа, Маньянти и Орлина (Ahuja, Magnati, Orlin, 1993).

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

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

Еще по теме Примечания и дополнительная литература:

  1. Дополнительная литература
  2. Дополнительная литература
  3. Дополнительная литература
  4. Дополнительная литература
  5. Дополнительная литература
  6. Дополнительная литература
  7. Дополнительная литература
  8. Дополнительная литература
  9. Дополнительная литература
  10. Дополнительная литература