4. Максимальный поток между каждой паров вершин

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

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

Как было отмечено во введении, эта задача может быть решена просто с помощью задачи о максимальном потоке (от для всех пар вершин Однако такой метод излишне трудоемок, поэтому мы изложим здесь алгоритм Гомори и Ху [14], который в случае неориентированных графов намного более эффективен. Так как этот алгоритм использует два важных понятия, то мы сначала обсудим их, чтобы сделать более ясным описание самого алгоритма.

4.1. Потоковая эквивалентность

Теорема 4. Пусть — значение максимального потока от вершины к вершине графа (Так как G - неориентированный граф, то ). Эти потоки удовлетворяют, соотношению

Доказательство. Если минимальный разрез, даюппга т. е.

то при выполняется неравенство так как является также разрезом, отделяющим от а при справедливо неравенство так как является также разрезом, отделяющим от Отсюда немедленно вытекает теорема.

Повторно применяя неравенство (11.8) к потокам в скобках из (11.8), получим

для любой последовательности вершин

Если теперь рассмотреть гипотетический полный граф вершииами и взять в качестве «длины» ребра максимальный поток между соответствующими вершинами из то эти «длины» можно использовать для построения «длиннейшего остова» графа применяя один из методов построения кратчайшего (или длиннейшего) остова, приведенных в гл. 7. В соответствии с (11.9) можно сказать, что поток больше или равен, чем «длина» кратчайшего ребра, лежащего на единственной цепи в из Если, однако, больше, чем «длина» кратчайшего ребра, то удаление этого ребра и добавление даст новое

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