Глава 22. Потоки в сетях. что X выиграет все свои оставшиеся игры), и должно существовать ребро (без про­пускной способности)

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

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

> 22.80. Покажите, что для сетей с относительно низкими границами на пропускные способности ребер задача определения минимального потока (которая выдерживает границы) сводится к задаче о максимальном потоке (см. упражнение 22.79).

•••22.81. Докажите, что задача о максимальном потоке в st-сетях сводится к задаче о мак­симальном потоке в неориентированных сетях, либо найдите алгоритм вычисления максимального потока в неориентированных сетях, время выполнения которого в худ­шем случае значительно лучше, чем аналогичный параметр алгоритмов, исследован­ных в разделах 22.2 и 22.3.

> 22.82. Найдите все сочетания с пятью ребрами для двудольного графа, представлен­ного на рис. 22.37.

22.83. Расширьте программу 22.7 таким образом, чтобы можно было пользоваться символическими именами вершин вместо цифровых обозначений (см. программу 17.10).

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

22.85. Мы можем интерпретировать пример на рис. 22.3 как предпочтение студента на выбор работы и предпочтение работодателя на выбор студентов, причем оба они могут и не быть взаимными. Применимо ли сведение, описанное в тексте, к ориенти­рованной задаче двудольного сочетания, которая вытекает из этой интерпретации, где ребра двудольного графа направлены (в обоих направлениях) из одного множества в другое? Докажите, что это так, либо приведите встречный пример.

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

22.87. Покажите в стиле рис. 22.28, работу алгоритма выталкивания превосходящего сетевого потока, использующего очередь FIFO, на сети двудольного сочетания, пока­занной на рис. 22.38.

о 22.88. Расширьте таблицу 22.3 таким образом, чтобы она включала различные алгорит­мы вытеснения превосходящего потока.

• 22.89. Предположим, что в задаче двудольного сочетания имеются два множества раз­
мерами S и Т, при этом S«T. Дайте как можно более четкую границу времени ре­
шения этой задачи в худшем случае для сведения, определяемого свойством 22.19, и
реализации алгоритма Форда-Фалкерсона, использующей построение максимальных
аугментальных путей (см. свойство 22.8).

• 22.90. Выполните упражнение 22.89 для реализации алгоритма выталкивания превос­
ходящего потока с использованием очереди FIFO (см. свойство 22.13).