Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 22. Потоки в сетях. образно использовать существующий класс максимального потока для решения такой задачи и переходить к решению следующей задачи
|
|
образно использовать существующий класс максимального потока для решения такой задачи и переходить к решению следующей задачи. Если производительность остается критической проблемой, мы можем провести исследование различных алгоритмов вычисления максимальных потоков и их реализаций или использовать их поведение как отправную точку для разработки более совершенного алгоритма специального назначения. Общая модель решения задач устанавливает верхнюю границу, которой мы можем либо удовлетвориться, либо попытаться ее улучшить, и обеспечивает множество реализаций, которые продемонстрировали свою эффективность при решении других многочисленных задач.
Далее мы обсудим задачи, имеющие отношение к связности графов. Прежде чем принимать решение использовать алгоритмы вычисления максимального потока для решения задачи о связности графа, мы исследуем возможность применения теоремы о максимальных потоках и минимальных сечениях, чтобы завершить работу, начатую в главе 18, т.е. получить доказательства базовых теорем, имеющих отношение к путям и сечениям в неориентированных графах. Эти доказательства являются дальнейшим свидетельствованием, подчеркивающим фундаментальное значение теоремы о максимальных потоках и минимальных сечениях.
Свойство 22.20. (Теорема Менгера). Минимальное число ребер, удаление которых разъединяет две вершины орграфа, равно максимальному числу не пересекающихся по ребрам (edge-disjoint) путей между этими двумя вершинами.
Доказательство: Пусть задан граф, определить транспортную сеть с теми же самыми вершинами и ребрами, при этом всем ребрам присваиваются значения пропускных способностей, равные 1. По свойству 22.2 любую st-сеть мы можем представить как множество не пересекающихся по ребрам путей из s в t, при этом число таких путей равно величине потока. Пропускная способность любого st-сечения равна кардинальному числу сечения. С учетом всех этих фактов, теорема о максимальных потоках и минимальных сечениях дает результат, представленный в формулировке свойства. ■
Соответствующий результат для неориентированных графов, для связности вершин в орграфах и неориентированных графах, предусматривает применение концепции сведения, подобное рассмотренному в тексте и приложениях (упражнения 22.94-22.96).
Обратимся теперь к алгоритмическим проблемам, порождаемым зависимостью между потоками и связностью, которая устанавливается теоремой о максимальных потоках и минимальных сечениях. Свойство 22.5, по-видимому, представляет собой один из важнейших результатов (задача о минимальном сечении сводится к задаче о максимальном потоке), однако обратное утверждение не доказано (см. упражнение 22.47). Здравый смысл подсказывает нам, что располагая информацией о минимальном сечении, легче решать задачу определения максимального потока, однако пока никому еще не удалось показать, почему это так. Этот базовый пример подчеркивает необходимость действовать осторожно при сведении одних задач к другим.
В то же время, мы все еще можем использовать алгоритмы вычисления максимального потока для решения различных задач о связности. Например, они полезны при решении первых нетривиальных задач, с которыми мы сталкивались в главе 18.
Реберная связность. Каким должно быть минимальное число ребер, которые необходимо удалить с тем, чтобы разделить заданный граф на две части? Найти множество ребер с минимальным числом элементов, обеспечивающее такое разделение.
Часть 5. Алгоритмы на графах
Вершинная связность. Каким должно быть минимальное число вершин, которые необходимо удалить с тем, чтобы разделить заданный граф на две части? Найти множество вершин с минимальным числом элементов, обеспечивающее такое разделение.
Эти задачи существуют также и в отношении орграфов, таким образом, в общем случае мы должны рассмотреть четыре задачи. Как и в случае теоремы Менгера, мы исследуем одну из них во всех подробностях (реберная связность в неориентированных графах), а остальные оставим читателям на самостоятельную проработку.
Свойство 22.21. Время, необходимое для определения реберной связности в неориентированных графах, есть О(Е2).
Доказательство: Мы можем вычислить минимальный размер любого сечения, которое разделяет две заданных вершины, за счет вычисления максимального потока в st-сети, построенной на базе графа с назначением единичной пропускной способности каждому ребру. Реберная связность равна минимальному из этих значений на всех парах вершин.
Нет необходимости, однако, выполнять вычисления для всех пар вершин. Пусть на графе s* есть вершина с минимальной степенью. Обратите внимание на то, что степень вершины s* не может быть больше 2E/V. Рассмотрим минимальное сечение этого графа. По определению, число ребер в сечении равно реберной связности графа. Вершина s* появляется в одном из множеств вершин сечения, а в другое множество должна входить некоторая вершина t, так что размер любого минимального сечения, разделяющего вершины s* и t, должен быть равен реберной связности графа. Следовательно, если мы решим у— 1 задач о минимальном потоке (используя s* как исток и любую другую вершину как сток), полученная величина минимального потока будет являться связностью рассматриваемой сети.
Теперь любой алгоритм вычисления максимального потока с использованием аугментальных путей с вершиной s* в качестве истока требует вычисления максимум 2E/V путей; таким образом, если мы используем метод, требующий самое большее Е шагов для определения аугментального пути, получаем самое большее (V- 1){2E/V)E для определения реберной связности, откуда и следует искомый результат. ■
Этот метод, в отличие от всех других примеров из этого раздела, не есть сведение одной задачи к другой, но он дает практический алгоритм для вычисления реберной связности. И опять-таки, аккуратная настройка реализации вычислений максимального потока на эту конкретную задачу позволяет повысить производительность - мы можем решить эту задачу за время, пропорциональное VE (см. раздел ссылок). Доказательство свойства 22.21 служит примером более общего понятия эффективного (выполняемого за полиномиальное время) сведения, с которым мы впервые столкнулись в разделе 21.7 и которое играет существенную роль в теории алгоритмов, исследуемых в части 8. Такое сведшие доказывает не только то, что задача принадлежит к числу решаемых, но и предлагает алгоритм для ее решения - т.е. важный первый шаг при решении новой комбинаторной задачи.
Мы завершим этот раздел анализом строгой математической формулировки задачи о максимальном потоке, используя средства линейного программирования (см. раздел 21.6). Это упражнение полезно тем, что оно помогает проследить связи с другими задачами, которые также могут быть четко сформулированы.
Глава 22. Потоки в сетях
Формулировка этой задачи достаточно проста: мы рассматриваем систему неравенств, в которой каждому ребру соответствует одна переменная величина, каждому ребру соответствуют два неравенства и каждой вершине соответствует одно уравнение. Значение переменной есть величина потока в ребре, неравенства указывают на то, что величина потока в ребре должна принимать значение в пределах от 0 до пропускной способности этого ребра, а уравнение указывает на то, что суммарный поток в ребрах, которые ведут в некоторую конкретную вершину, должен быть равен суммарному потоку в ребрах, которые исходят из этой вершины.
Рисунок 22.39 служит примером такого построения. Любая задача о максимальном потоке таким способом может быть преобразована в задачу линейного программирования (в LP-задачу). Линейное программирование представляет собой гибкий подход к решению комбинаторных задач, и многочисленные задачи, которые мы изучаем, могут быть сформулированы как линейные программы. Тот факт, что задачи о максимальном потоке легче поддаются решению, чем LP-задача, можно объяснить тем фактом, что в формулировке задач о максимальном потоке как LP-задач употребляются ограничения, имеющие специфическую структуру, которая характерна не для всех LP-задач.
Даже если LP-задача в общем виде намного сложнее, чем задачи специального вида, такие как задача о максимальном потоке, существуют мощные алгоритмы, которые могут эффективно решать LP-задачи. Время выполнения этих алгоритмов в худшем случае почти наверняка превосходит время выполнения в худшем случае специальных алгоритмов, которые мы рассматривали выше, однако громадный опыт, накопленный за последние несколько десятилетий, показал их эффективность при решении задач этого типа, которые часто возникают на практике.
Построение, представленное на рис. 22.39, служит доказательством того, что задача о максимальном потоке сводится к соответствующей LP-задаче, если мы не настаиваем, что величины потоков должны быть целыми числами. Мы будем подробно рассматривать LP-задачи в части 8, где и опишем способ преодолеть затруднения, связанные с тем, что формулировка задачи о
РИСУНОК 22.39. ФОРМУЛИРОВКА ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ В ТЕРМИНАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Эта линейная программа эквивалентна задаче о максимальном потоке применительно к демонстрационному примеру, показанному на рис. 22.5. В рассматриваемом случае на каждое ребро приходится одно неравенство (которое показывает, что поток в некотором ребре не может превосходить его пропускной способности) и одно равенство на каждую вершину (которое показывает, что приток должен быть равен истечению из этой вершины). В этой сети мы используем фиктивное ребро, ведущее из стока в исток, в соответствии с изложенным при анализе свойства 22.2.
Часть 5. Алгоритмы на графах
максимальном потоке в терминах линейного программирования не содержит условия, требующего, чтобы результаты ее решения были выражены в целых числах.
Этот контекст дает нам возможность воспользоваться жесткой математической основой, в рамках которой мы можем искать решения задач более общего вида и создавать более совершенные алгоритмы решения этих задач. Задача о максимальном потоке легко поддается решению, она обладает своего рода гибкостью, о чем говорят примеры, приведенные в данном разделе. Далее мы будем изучать более сложные задачи (но, тем не менее, они уступают по сложности LP-задачам), которые охватывают определенный класс практических задач. Мы обсудим разновидности решений в рамках этих моделей с возрастающим уровнем абстракции в конце этой главы, тем самым заложив основу для их полного анализа в части 8.