Упражнения. > 22.21.Найдите минимальное сечение в транспортной сети, показанной на рис

22.19. Покажите в стиле рис. 22.13 столько различных последовательностей аугмен­
тальных путей, сколько вы их сможете найти в транспортной сети, показанной на рис.
22.10.

22.20. Покажите в стиле рис. 22.15 все сечения транспортной сети, показанной на рис.
22.10, их разделяющие множества и пропускные способности.

> 22.21. Найдите минимальное сечение в транспортной сети, показанной на рис. 22.11.

о 22.22. Предположим, что в некоторой транспортной сети достигнут баланс пропуск­ных способностей (для каждого внутреннего узла общая пропускная способность вхо­дящих ребер равна общей пропускной способности исходящих ребер). Использует ли когда-нибудь алгоритм Форда-Фалкерсона обратные ребра? Докажите, что использует, либо приведите встречный пример.

22.23. Определите максимальный поток для транспортной сети, представленной на рис. 22.5, в которой, по меньшей мере, величина одного потока, не является целым числом.

> 22.24. Разработайте реализацию алгоритма Форда-Фалкерсона, который использует
обобщенную очередь вместо очереди с приоритетами (см. раздел 18.8).

> 22.25. Докажите, что число аугментальных путей, необходимых для реализации алго­
ритма Форда-Фалкерсона, есть не более чем в V раз уменьшенное целое число, ко­
торое превышает отношение пропускной способности наибольшего ребра к пропус­
кной способности наименьшего ребра.

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

> 22.27. Представьте пример сети, подобной изображенной на рис. 22.19, для которой
алгоритм поиска кратчайшего аугментального пути обладает поведением в худшем
случае подобным представленному на рис. 22.19.

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

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