Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 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.96. Расширьте полученное вами доказательство упражнения 22.95 на неориентиро
22.97. Постройте класс реберной связности для АТД графа из главы 17, конструктор 22.98. Расширьте полученное вами решение упражнения 22.97 с таким расчетом, чтобы
• 22.99. Разработайте алгоритм вычисления реберной связности орграфов (минималь • 22.100. Разработайте алгоритм, в основе которых лежат решения, полученные в уп 22.101. Покажите, как можно выявить вершинную связность орграфа путем решения V lgV-задач о максимальном потоке в сети с единичной пропускной способностью ребер. Указание: Воспользуйтесь теоремой Менгера и двоичным поиском. о 22.102. Проведите эмпирические исследования на базе полученного вами решения упражнения 22.97 с целью получить сведения о связности различных графов (см. упражнения 17.63-17.76). > 22.103. Дайте формулировку задачи о максимальном потоке в транспортной сети, представленной на рис. 22.10, в терминах линейного программирования. о 22.112. Сформулируйте в концепциях линейного программирования задачу двудольного сочетания, представленную на рис. 22.37.
|