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

15.7. Потоки в транспортной сети

Транспортная сеть N есть связный ориентированный граф, который не имеет петель и удовлетворяет следующим условиям: 1. Существует только одна вершина с нулевой полустепенью захода; эта вершина называется источником и обозначается через

2. Существует только одна вершина с нулевой полустепенью исхода; эта вершина называется стоком и обозначается через

3. Каждому ориентированному ребру в сети N сопоставлено неотрицательное вещественное число, называемое пропускной способностью ребра; оно обозначается через или Если не существует ребра , ориентированного из i в то мы доопределяем

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

Потоком в транспортной сети N является функция, сопоставляющая каждому ребру неотрицательное вещественное число так, что удовлетворяются следующие условия:

Значение потока в ребре можно рассматривать как скорость, с которой материал перемещается вдоль при потоке

Рис. 15.17. Транспортная сеть.

Условие (15.32), называемое ограничением по пропускной способности, требует, чтобы скорость потока вдоль ребра не превосходила пропускной способности ребра. Условие (15.33), называемое условием сохранения, требует, чтобы для каждой вершины , исключая источник и сток, скорость, с которой материал доставляется в , была бы равна скорости, с которой он удаляется из

Пример транспортной сети N с потоком f представлен на рис. 15.17. На нем рядом с каждым ребром приведены пропускная способность и поток в указанном порядке.

Величина потока f, обозначаемая через определяется выражением

    (15.34)

Далее мы покажем, используя условие сохранения, что

    (15.35)

Это будет только подтверждением интуитивно очевидного факта, что ввиду условия сохранения общее количество материала, выходящего из источника, равно общему количеству материала, входящего в сток.

Говорят, что поток в транспортной сети N максимален, если не существует такого потока f в N, что

В следующем подразделе мы докажем теорему Форда и Фалкерсона о максимальном потоке и минимальном разрезе, после чего рассмотрим помечивающий алгоритм Форда и Фалкерсона определения максимального потока в транспортной сети. В заключение мы докажем теоремы Менгера, используя теорему о максимальном потоке и минимальном разрезе.

15.7.1. Теорема о максимальном потоке и минимальном разрезе

Будем говорить, что разрез в транспортной сети N разделяет источник s и сток t, если . Такой разрез будем называть -разрезом. Пропускная способность разреза определяется выражением

    (15.36)

Отметим, что пропускная способность ребер, которые ориентированы из S в S, не увеличивает пропускную способность разреза Мы обозначим через сумму потоков в ребрах, ориентированных из S в S. Величина определяется аналогично.

Например, рассмотрим разрез в транспортной сети, изображенной на рис. 15.17, где .

Ребрами, ориентированными из S в S, являются ребра Следовательно,

Теорема 15.7. Для любого потока и любого -разреза в транспортной сети

    (15.37)

Доказательство. Из определений потока и величины потока имеем

Суммируя эти равенства по всем вершинам в S, получим

    (15.38)

В левой части этого равенства для появляются точно по одному разу и поэтому взаимно погашаются. Поэтому выражение (15.38) упрощается до

Таким образом,

Отметим, что выражение (15.34) является частным случаем выражения (15.37).

Следствие 15.7.1. Для любого потока и любого -разреза в транспортной сети

    (15.39)

Доказательство. Так как любая величина неотрицательна то из выражения (15.37) получим

Ребро будем называть -насыщенным, и -ненасыщенным в противном случае; оно будет -положительным, если и -нулевым, если

Отметим, что знак равенства в выражении (15.39) достигается тогда и только тогда, когда Другими словами, тогда и только тогда, когда все ребра, ориентированные из S в являются -насыщенными, а ребра, ориентированные из S в -нулевыми, -разрез К в транспортной сети N является минимальным, если не существует такого -разреза К в N, что

Следствие 15.7.2. Пусть — поток, такой -вразрез, что . Тогда -максимальный поток, минимальный -разрез.

Доказательство. Пусть максимальный поток, а К— минимальный -разрез. Из следствия 15.7.1. имеем Поэтому мы получаем . Так как по предположению следствия то отсюда следует, что Таким образом, -максимальный поток, минимальный -вразрез.

Перейдем к доказательству того, что величина максимального потока фактически равна пропускной способности минимального разреза. Рассмотрим транспортную сеть с потоком Пусть цепочка

является путем в N из источника в какую-либо вершину V. Отметим, что Р — необязательно ориентированный путь. Ребро пути Р называется прямым ребром пути Р, если оно ориентировано из Иначе оно называется обратным ребром пути Р. Пусть для каждого ребра пути Р

    

Сопоставим пути Р неотрицательное число определяемое выражением

    (15.41)

Мы назовем путь -ненасыщенным, если все прямые ребра пути являются -ненасыщенными, а все обратные ребра пути — -положи-телъными.

-путь Р называется -дополняющим путем, если Р является -ненасыщенным. Из выражений (15.40) и (15.41) следует, что для -пути Р неравенство справедливо тогда и только тогда, когда Р является -дополняющим. Для данного -пути Р в сети N мы можем определить новый поток следующим образом:

Очевидно, что

Таким образом, тогда и только тогда, когда Р является -дополняющим путем. Другими словами, поток не максимален, если существует -дополняющий путь.

В качестве примера рассмотрим сеть N, изображенную на рис. 15.17. Пусть поток будет таким, каким он показан на этом рисунке. В пути состоящем из ребра — прямые, а — единственное обратное ребро. По отношению к потоку имеем равенство Следовательно,

Рис. 15.18.

Так как то Р является дополняющим путем. Измененный на пути Р поток представлен на рис. 15.18. Отметим, что f получен увеличением потока на всех прямых ребрах пути Р на величину и его уменьшением на всех обратных ребрах пути Р на величину Потоки в остальных ребрах остаются неизменными.

Теорема 15.8. Поток в транспортной сети N максимален тогда и только тогда, когда в сети нет -дополняющих путей.

Доказательство. Необходимость. Если в N существует -дополняющий путь Р, то ясно, что — не максимальный поток, так как измененный на основе пути Р поток имеет большую величину, чем

Достаточность. Предположим, что N не содержит -дополняющего пути. Пусть S — множество всех вершин в N, до которых существуют -ненасыщенные пути из источника. Ясно, что Далее I? S, так как в N не существует -дополняющего пути.

Покажем, что доказывая (согласно следствию 15.7.2), что — максимальный поток, — минимальный разрез.

Рассмотрим ориентированное ребро для которого Так как то существует -ненасыщенный -путь Q. Ребро должно быть -насыщенным, так как иначе Q можно расширить и получить -ненасыщенный -путь, что невозможно, так как Аналогично мы можем показать, что каждое ребро ориентированное из S в S, должно быть -нулевым.

Таким образом, Следовательно, Тогда из следствия 15.7.2 вытекает, — максимальный поток, — минимальный разрез.

В ходе доказательства приведенной выше теоремы мы установили следующий хорошо известный результат Форда и Фалкерсона [15.44], а также Элиаса, Файнштайна и Шеннона [15.45].

Теорема 15.9. (Теорема о максимальном потоке и минимальном разрезе.) В транспортной сети величина максимального потока равна пропускной способности минимального разреза.

Теорему о максимальном потоке и минимальном разрезе можно использовать для доказательства нескольких комбинаторных результатов. Мы рассмотрим один из этих результатов в подразделе 15.7.4. Другие приведены в работах [15.1, 15.46].

15.7.2. Помечивающий алгоритм Форда и Фалкерсона

Рассмотрим теперь алгоритм Форда и Фалкерсона [15.44] для определения максимального потока в транспортной сети. Этот алгоритм, основанный на теореме 15.8, состоит из двух фаз.

На первой фазе по заданному потоку мы, используя помечивающую процедуру, проверяем, существует ли -дополняющий путь. Если такого пути не существует, то, согласно теореме 15.8, данный поток максимален. Иначе мы переходим ко второй фазе, в которой, используя метки, полученные в первой фазе, определим — дополняющий путь Р — и получим измененный на основе пути Р поток Затем мы повторим фазу 1 для нового потока Отметим, что

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

Первая фаза начинается с пометки источника парой Здесь значение несущественно. Помечивание остальных вершин происходит в соответствии со следующими правилами:

Предположим, что вершина и помечена, а вершина v нет. Пусть е — ребро, связывающее и и

Прямое помечивание. Если , то прямое помечивание v из и вдоль ребра возможно, если Если такое помечивание осуществлено, то v получает метку где

Обратное помечивание. Если , то обратное помечивание v из и вдоль ребра возможно, если Если такое помечивание осуществлено, то и получает метку где

На первой фазе вершины помечаются только однажды. Эта фаза завершается, когда 1) вершина t получает метку либо 2) вершина t не помечена и ни одну из вершин больше нельзя пометить.

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

Алгоритм 15.9. Максимальный поток в транспортной сети (Форд и Фалкерсон).

S1. Выбрать какой-либо поток в данной транспортной сети. Мы можем положить для каждого ребра в

S2. (Начинается фаза 1.) Пометить s парой

S3. Если существует непомеченная вершина, которую можно пометить с помощью прямого или обратного помечивания, то выбрать одну такую вершину и, пометить ее и перейти к шагу Иначе идти к шагу

S4. Если то идти к шагу (Фаза 1 завершена.) Иначе идти к шагу

S5. (Начинается фаза 2.) Пусть метка вершины v есть Тогда выполнить следующие действия:

1) если то положить

2) если то положить

S6. Если то удалить все метки (фаза 2 завершена) и идти к шагу Иначе положить и идти к шагу

S7. (Полученный — максимален.) HALT.

Проиллюстрируем работу вышеприведенного алгоритма.

Рассмотрим транспортную сеть N, представленную на рис. 15.19. На нем рядом с каждым ребром показаны значения соответственно. В качестве начального потока принимаем для всех ребер в сети N. Начиная с метки для источника s, мы помечаем (шаг алгоритма 15.9) вершины а, b, с, d и t в указанном порядке. Получаем метки

Фаза 1 завершается, так как вершина t уже помечена. В фазе 2 мы определяем дополняющий путь Р и измененный поток

Рис. 15.19. Сеть для иллюстрации помечивающего алгоритма Форда — Фалкерсона.

Первый символ в метке t есть Это означает, что в пути Р вершина b предшествует вершине t. Первый символ в метке b указывает, что вершина а предшествует вершине b в пути Р. Аналогично мы видим, что s предшествует а пути Р. Таким образом,

Все ребра в Р являются прямыми. Поэтому для получения измененного потока мы увеличиваем потоки во всех ребрах пути Р на . Поток имеет величину, равную 2, и изображен на рис. 15.20, а.

Мы стираем метки всех вершин. Имея поток мы получаем затем новое множество меток, показанных на рис. 15.20, а. Добавляющий путь по отношению к состоит из вершин s, с, d, t в указанном порядке. Все ребра в этом пути Р являются прямыми. Потоки в этих ребрах увеличиваются на 2. Получающийся поток показан на рис. 15.20, б.

Новое множество меток, основанное на показано на рис. 15.20, б. Дополняющий путь по отношению к состоит из вершин s, с, b, a, d, t. Ребро, соединяющее вершины а и b, является обратным ребром в этом пути. Все другие ребра пути являются прямыми. Увеличим потоки в прямых ребрах на 1 и настолько же уменьшим поток в обратном ребре. Получающийся в результате поток представлен на рис. 15.20, b.

Имея мы переходим к помечиванию вершин. Этот процесс завершается в состоянии, показанном на рис. 15.20, в, когда вершина t еще не помечена. Таким образом, не существует дополняющего пути по отношению к потоку Поэтому — максимальный поток.

Рис. 15.20. Иллюстрация полечивающего алгоритма Форда — Фалкерсона.

Пусть S — множество вершин, помеченных на рис. 15.20, в. Тогда Поэтому из доказательства теоремы 15.8 ясно, что разрез является минимальным разрезом,

15.7.3. Модификация Эдмондса и Карпа алгоритма помечивания

В алгоритме Форда — Фалкерсона, который мы описали в предыдущем подразделе, вершины можно помечать в произвольном порядке. Другими словами, выбор дополняющего пути (когда он существует) делается произвольным образом. Проиллюстрируем на примере проблему, к которой может привести произвольность выбора.

Рис. 15.21.

Рассмотрим транспортную сеть N, изображенную на рис. 15.21. Предположим, что мы начинаем выполнять помечивающий алгоритм с нулевого потока и поочередно используем пути в качестве дополняющих путей. На каждом шаге величина потока увеличивается точно на 1, а максимальный поток величиной достигается после дополняющих шагов. Таким образом, число вычислительных шагов, выполняемых в этом случае, не ограничено функцией числа вершин и ребер сети N. Это число есть фактически функция от пропускной способности М, которая может быть произвольно большой.

Более того, Форд и Фалкерсон [15.1] показали, что их алгоритм может не найти решения, если пропускные способности ребер являются иррациональными числами. Они привели пример, в котором величина потока стремится к величины максимального потока при бесконечном увеличении числа шагов.

Для устранения этого недостатка Эдмондс и Карп [15.4] предложили усовершенствование помечивающего алгоритма: на каждом шаге поток увеличивается вдоль кратчайшего пути. Под кратчайшим путем здесь понимается путь, имеющий наименьшее число ребер. Очевидно, что кратчайший дополняющий путь будет выбран, если в процедуре помечивания мы рассматриваем вершины по правилу «первым помечен — первым рассмотрен», т. е. если вершина v помечена до вершины , то мы рассматриваем вершину v до вершины . Рассмотрение помеченной вершины v означает помечивание (когда это возможно) всех непомеченных вершин, смежных

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

Рассмотрим поток в транспортной сети N. Пусть

дополняющий путь. Напомним, что

Таким образом, для некоторого . Тогда соответствующее ребро ; называется узким местом.

Предположим, что помечивающий алгоритм начинает с начального потока и строит последовательность потоков

Отметим, что, когда ребро является узким местом в прямом направлении в дополняющем пути, оно становится насыщенным при увеличении потока. Если является узким местом в обратном направлении, то при таком возрастании поток через уменьшается до нуля. Это замечание приводит к следующему результату:

Лемма 15.7. Если — узкое место в прямом (обратном) направлении в дополняющем пути, который меняет как на так и то существует такое что используется как обратное (прямое) ребро в дополняющем пути, который меняет на

Путь — длина кратчайшего -ненасыщенного пути из в v. Этот путь, конечно, не обязательно будет ориентированным. Далее заметим, что ребро используется как прямое ребро в пути, только если оно не насыщено, т. е. и ребро используется как обратное ребро, только если

Лемма 15.8. Для каждой вершины v и каждого

    (15.43)

Доказательство. Мы докажем соотношение (15.42). Соотношение (15.43) доказывается аналогично.

Предположим, что не существует -ненасыщенного пути из s в v. Тогда будем считать бесконечной и неравенство (15.42) выполняется тривиально. Поэтому предположим, что

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

    (15.44)

так как кратчайший -ненасыщенный путь из за которым следует в прямом направлении, является -ненасыщенным путем из s в Очевидно, что в последнем случае

    (15.45)

В любом случае соотношение (15.44) выполняется.

Аналогично мы можем показать, что (15.44) верно, когда - используется как обратное ребро в пути Р.

Суммируя (15.44) для и замечая, что получим Таким образом, соотношение (15.42) доказано.

Лемма 15.9. Если используется принцип «первый помечен — первый рассмотрен», используется как прямое (обратное) ребро в дополняющем пути, который меняет на и как обратное (прямое) ребро в дополняющем пути, который меняет на , то

Доказательство. Предположим, что ориентировано из и в v. Тогда

    (15.46)

так как используется как обратное ребро при увеличении Далее,

    (15.47)

так как используется как обратное ребро при увеличении Но и

    (15.48)

Тогда из выражений получим

Теорема 15.10. (Эдмондс и Карп.) Если в помечивающем алгоритме Форда — Фалкерсона каждое увеличение потока выполняется вдоль кратчайшего дополняющего путн, то максимальный поток можно получить не более чем после приращений величины потока, где — число ребер, число вершин в транспортной сети.

Доказательство. Рассмотрим какое-либо ребро , ориентированное из и в v. Рассмотрим далее такую последовательность потоков где что используется прямое ребро при увеличении и является узким местом в этот момент. Согласно лемме 15.7, существует такая последовательность

что используется как обратное ребро при увеличении .

По лемме . Поэтому . Так как то мы получаем или

Таким образом, можно использовать как узкое место в прямом направлении не более чем раз. Аналогично его можно использовать как узкое место в обратном направлении не более чем раз. Поэтому каждое ребро может служить узким местом не более чем раз. Поэтому общее число увеличений потока не превышает

В доказательстве приведенной выше теоремы не делается никаких предположений о природе пропускных способностей ребер, кроме их неотрицательности. Таким образом, из теоремы ясно, что если используется принцип «первый помечен — первый рассмотрен», то алгоритм 15.9 заканчивается для любых вещественных неотрицательных пропускных способностей за конечное число увеличений потока. Так как дополняющий путь можно найти за шагов, то из теоремы 15.10 следует, что алгоритм 15.9 имеет сложность .

В работе [15.47] описывается класс сетей, для которых необходимо увеличений потока при условии выполнения каждого увеличения вдоль кратчайшего дополняющего пути. Поэтому верхнюю границу в теореме 15.10 нельзя улучшить, если не рассматривать линейный коэффициент.

В работе [15.48] показано, как улучшить эффективность алгоритма 15.9, выделяя в одном из применений помечивающей процедуры все кратчайшие пути для увеличения потока. Эта идея подобна идее, использованной Хопкрофтом и Карпом [15.36] при построении максимального паросочетания в двудольном графе. В данном случае алгоритм имеет сложность

Недавно был представлен [15.49] алгоритм сложности Впоследствии авторы работы [15.50] дали более простой алгоритм со сложностью Этот и подобные алгоритмы описаны в работе [15.51].

Была изучена [15.37] сложность алгоритма Диница для особого класса транспортных сетей. Как мы упоминали ранее в разд. 15.5, этот результат был использован, чтобы показать, что максимальное паросочетание в двудольном графе можно построить за время, пропорциональное

15.7.4. Теоремы Менгера

В этом разделе мы докажем теоремы Менгера для ориентированных и неориентированных графов, используя теорему о максимальном потоке и минимальном разрезе. Напомним, что мы сформулировали ранее теоремы Менгера (8.9 и 8.12) для неориентированных графов без доказательства. В последующем изложении

мы для целей общности будем допускать возможность того, что источник имеет ненулевую полустепень захода, а сток — ненулевую полустепень исхода. Наше доказательство теорем Менгера основано на следующем результате:

Теорема 15.11. Пусть N — транспортная сеть с источником s и стоком в которой каждое ребро имеет единичную пропускную способность. Тогда 1) величина максимального потока в сети N равна максимальному числу не пересекающихся по ребрам ориентированных -путей в сети N; 2) пропускная способность минимального разреза в сети N равна минимальному числу q ребер, удаление которых разрушает все ориентированные -пути в сети

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

    (15.49)

Пусть набор не пересекающихся по ребрам -путей в графе N. Определим такой поток что

Ясно, что Так как максимальный поток, то мы имеем

    (15.50)

Объединяя выражения (15.49) и (15.50), получим

2. Пусть — минимальный -разрез в графе N. Удалим из N множество ребер . Тогда в получающемся ориентированном графе не будет одного ориентированного -пути. Поэтому

    (15.51)

Пусть Z — множество из q ребер, удаление которых разрушает все ориентированные -пути в множество всех вершин, достижимых из s с помощью ориентированного пути, не содержащего ребра из Z. Ясно, что -разрез в

Поэтому

    (15.52)

Объединяя выражения (15.51) и (15.52), получим

Теорема 15.12. Пусть s и — две вершины в ориентированном графе G. Тогда максимальное число не пересекающихся по ребрам ориентированных -путей в G равно минимальному числу ребер, удаление которых разрушает все ориентированные -пути в графе

Доказательство. Построим из графа G транспортную сеть N с источником s и стоком приписывая каждому ребру графа G единичную пропускную способность. Тогда доказываемая теорема является следствием теоремы 15.11 и теоремы о максимальном потоке и минимальном разрезе.

Для неориентированного графа G пусть ориентированный граф, полученный заменой каждого ребра графа G парой противоположно ориентированных ребер, инцидентных тем же вершинам, что и е. Можно легко показать, что 1) существует взаимнооднозначное соответствие между путями в графе G и ориентированными путями в графе и 2) для любых двух вершин s и t минимальное число ребер, удаление которых из графа разрушает все -пути в графе G, равно минимальному числу ребер, удаление которых разрушает все ориентированные пути в графе Из этих замечаний вытекает справедливость неориентированного варианта теоремы 15.12.

Теорема 15.13. Пусть s и две вершины неориентированного графа G. Максимальное число не пересекающихся по ребрам -путей в графе G равно минимальному числу ребер, удаление которых разрушает все -пути в графе G. Вершинные аналоги теорем 15.12 и 15.13 доказываются следующим образом: Пусть s и — две несмежные вершины в ориентированном графе . Построим из графа G ориентированный граф G следующим образом:

1. Расщепим вершину на две новые вершины соединим их ориентированным ребром .

2. Заменим каждое ребро графа G с конечной вершиной на новое ребро, имеющее и в качестве конечной вершины.

3. Заменим каждое ребро графа G с начальной вершиной на новое ребро, имеющее v в качестве начальной вершины.

Рис. 15.22. а — граф С; б — граф С.

Граф G и соответствующий ему граф представлены на рис. 15.22. Нетрудно доказать, что:

1. Каждый ориентированный -путь в графе G соответствует ориентированному -пути в графе G, который получается стягиванием всех ребер вида и, наоборот, каждый ориентированный -путь в графе G соответствует -пути в графе полученному расщеплением всех вершин пути, отличных от S и

2. Два ориентированных -пути в графе G не пересекаются по ребрам тогда и только тогда, когда соответствующие им пути в графе G не пересекаются по вершинам.

3. Максимальное число не пересекающихся по ребрам ориентированных -путей в графе G равно максимальному числу не пересекающихся по вершинам ориентированных -путей в графе

4. Минимальное число ребер, удаление которых разрушает все ориентированные -пути в графе равно минимальному числу вершин, удаление которых разрушает все ориентированные -пути в графе

Из этих замечаний следует справедливость вершинного аналога теоремы 15.12.

Теорема 15.14. Пусть s и t — две несмежные вершины в ориентированном графе G. Тегда максимальное число не пересекающихся по вершинам ориентированных -путей в графе G равно минимальному числу вершин, удаление которых разрушает все ориентированные -пути в графе

Теореме 15.13 соответствует следующая теорема:

Теорема 15.15. Пусть s и — две несмежные вершины в неориентированном графе G. Тогда максимальное число не пересекающихся по вершинам -путей в графе G равно минимальному числу вершин, удаление которых разрушает все -пути в графе

Доказательство. Достаточно применить теорему 15.14 к графу

Стандартной ссылкой на теорию потоков в сетях является ссылка на работу [15.1], в которой рассматривается также задача поиска потока минимальной стоимости. Эти вопросы излагаются также в работах [15.7-15.9, 15.46, 15.52, 15.53].

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