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

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

••22.92. Докажите, что время прогона метода, описанного в упражнении 22.91, есть О(√ V E) для поиска в ширину.

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

о 22.94. Докажите теорему Менгера (свойство 22.20) для неориентированных графов.

• 22.95. Докажите, что минимальное число вершин, удаление которых нарушает связь
двух вершин в орграфе, равно максимальному числу путей между этими двумя верши­
нами, не пересекающимися по вершинам. Указание. Воспользуйтесь преобразованием,
предусматривающим разделение вершин, подобное показанному на рис. 22.32.

• 22.96. Расширьте полученное вами доказательство упражнения 22.95 на неориентиро­
ванные графы.

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

22.98. Расширьте полученное вами решение упражнения 22.97 с таким расчетом, чтобы
в векторе, задаваемом пользователем, содержалось минимальное множество ребер,
способных разрушить связность графа. На какой размер этого вектора должен рас­
считывать пользователь?

• 22.99. Разработайте алгоритм вычисления реберной связности орграфов (минималь­
ное число ребер, удаление которых из орграфа лишает его свойства сильной связно­
сти). Постройте реализацию класса, основанного на предложенном вами алгоритме
для АТД орграфа, описание которого приводится в главе 19.

• 22.100. Разработайте алгоритм, в основе которых лежат решения, полученные в уп­
ражнениях 22.95 и 22.96, касающиеся вершинной связности орграфов и неориентиро­
ванных графов. Постройте реализации классов, соответственно, на базе алгоритма для
АТД орграфа, описание которого приводится в главе 19, и на базе алгоритма для АТД
графа, описание которого приводится в главе 17 (см. упражнения 22.97 и 22.98).

22.101. Покажите, как можно выявить вершинную связность орграфа путем решения V lgV-задач о максимальном потоке в сети с единичной пропускной способностью ре­бер. Указание: Воспользуйтесь теоремой Менгера и двоичным поиском.

о 22.102. Проведите эмпирические исследования на базе полученного вами решения уп­ражнения 22.97 с целью получить сведения о связности различных графов (см. упраж­нения 17.63-17.76).

> 22.103. Дайте формулировку задачи о максимальном потоке в транспортной сети, представленной на рис. 22.10, в терминах линейного программирования.

о 22.112. Сформулируйте в концепциях линейного программирования задачу двудоль­ного сочетания, представленную на рис. 22.37.