5. АЛГОРИТМЫ НА ГРАФАХ

Многие задачи теоретического и прикладного характера можно сформулировать в терминах неориентированных или ориентированных графов. В этой главе мы обсудим некоторые из основных задач на графах, решения которых полиномиально зависят (в смысле времени выполнения) от числа узлов и, следовательно, ребер графа. В основном мы будем заниматься задачами, в которых речь идет о связности графа. Сюда входят алгоритмы для нахождения остовных деревьев, двусвязных компонент, сильно связных компонент и путей между узлами. В гл. 10 мы изучим более сложные задачи о графах.

5.1. ОСТОВНОЕ ДЕРЕВО НАИМЕНЬШЕЙ СТОИМОСТИ

Пусть связный неориентированный граф, для которого задана функция стоимости, отображающая ребра в вещественные числа. Напомним, что остовным деревом для данного графа называется неориентированное дерево, содержащее все узлы графа. Стоимость остовного дерева определяется как сумма стоимостей его ребер. Наша цель — найти для остовное дерево наименьшей стоимости. Мы увидим, что остовное дерево наименьшей стоимости для графа с ребрами можно найти за время в общем случае и если достаточно велико по сравнению с числом узлов (см. упр. 5.3). Многие алгоритмы нахождения остовного дерева основаны на следующих двух леммах.

Лемма 5.1. Пусть связный неориентированный граф и остовное дерево для него. Тогда

(а) для любых двух узлов и из V путь между единствен и

(б) если к добавить ребро из то возникнет ровно один цикл.

Доказательство. Утверждение (а) тривиально, ибо если бы было более одного пути, то в был бы цикл.

Утверждение (б) тоже тривиально, ибо между концами добавляемого ребра уже был один путь.

Лемма 5.2. Пусть связный неориентированный граф и с — функция стоимости, заданная на его ребрах. Пусть произвольный остовный лес для Допустим, что ребро наименьшей стоимости в причем Тогда найдется остовное дерево для содержащее стоимость которого не больше стоимости любого остовного дерева для содержащего

Доказательство. Допустим противное и обозначим через остовное дерево для содержащее и не содержащее стоимость которого меньше стоимости любого остовного дерева для содержащего

По лемме добавление образует цикл (см. рис. 5.1). Этот цикл должен содержать такое ребро отличное от что По условию с

Рассмотрим граф образованный добавлением и удалением из нет циклов, поскольку единственный цикл был разорван удалением ребра Кроме того, все узлы в V все еще соединены, так как есть путь между Следовательно, остовное дерево для Так как то стоимость дерева не больше стоимости дерева Но содержит и и что противоречит минимальности дерева

Опишем алгоритм нахождения остовного дерева наименьшей стоимости для неориентированного графа Этот алгоритм по существу тот же, что и в примере 4.1. Он работает с набором непересекающихся множеств узлов. Каждое множество из представляет связное множество узлов, образующее остовное дерево в остовном лесу, представленном набором Ребра

Рис. 5.1. Цикл в графе О.

Рис. 5.2. Алгоритм построения остовного дерева наименьшей стоимости.

выбираются из в порядке возрастания стоимости. Ребра рассматриваются по очереди. Если принадлежат одному и тому же множеству из то ребро ( исключается из рассмотрения. Если принадлежат разным множествам (это означает, что еще не соединены), то сливаем их в одно множество и добавляем к множеству ребер, входящих в окончательное остовное дерево. Здесь можно воспользоваться алгоритмом объединения непересекающихся множеств, описанным в разд. 4.7. Применив лемму 5.2 и проведя несложную индукцию по числу выбранных ребер, заключаем, что это ребро содержится по крайней мере в одном остовном дереве наименьшей стоимости для

Алгоритм 5.1. Остовное дерево наименьшей стоимости (алгоритм Крускала)

Вход. Неориентированный граф с функцией стоимости с, заданной на его ребрах.

Выход. Остовное дерево наименьшей стоимости для

Метод. Программа приведена на рис. 5.2.

Пример 5.1. Рассмотрим неориентированный граф на рис. 5.3. Перечислим его ребра в порядке возрастания их стоимостей:

Разумеется, на самом деле на шаге 3 алгоритма 5.1 ребра не сортируются, а хранятся в виде сортирующего дерева, 2-3-дерева или какой-нибудь другой приемлемой структуры данных, пока они не потребуются. Сортирующее дерево из разд. 3.4 фактически дает идеальный способ реализации очереди с приоритетами. Повторное обращение в строке 6 с целью найти ребро наименьшей стоимости является основной операцией с Сортдеревом. Кроме того, число ребер, выбираемых в строке 6 для построения остовного дерева, часто меньше В таких ситуациях мы экономим время, поскольку никогда не упорядочиваем полностью.

Вначале каждое ребро находится в одноэлементном множестве, входящем в и состоящем из самого этого ребра. Наименьшую стоимость имеет ребро так что оно добавляется к дереву и множества в сливаются.

Затем рассматривается ребро Так как принадлежат разным множествам из добавляем к дереву и сливаем Далее добавляем и сливаем Добавляем также четвертое ребро и сливаем

Рис. 5.3. Неориентированный граф с указанными стоимостями его ребер.

Рис. 5.4. Последовательность шагов построения остовного дерева.

Затем рассматривается ребро Оба узла принадлежат одному и тому же множеству Следовательно, из идет путь из ребер, уже вошедших в остовное дерево, и потому не добавляется. Вся последовательность шагов приведена на рис. 5.4. Остовное дерево, получающееся в результате, изображено на рис.

Теорема 5.1. Алгоритм 5.1 находит остовное дерево наименьшей стоимости для связного графа Если в цикле, описанном строками 5—10, рассматривается ребер, то затрачивается время где Следовательно, алгоритм 5.1 занимает не более времени.

Доказательство. Корректность алгоритма вытекает непосредственно из леммы 5.2 и того факта, что строки 8 и 9 сохраняют узлы в том же самом множестве тогда и только тогда, когда

Рис. 5.5. Остовное дерево наименьшей стоимости.

они принадлежат одному и тому же дереву остовного леса, представленного набором

Для оценки времени допустим, что требуется итераций цикла в строках 5—10. Нахождение ребра наименьшей стоимости в (строка 6) занимает шагов, если реализуется очередью с приоритетами. Общее время нахождения всех множеств и содержащих у и до (строка 8), и замены их на их объединение (строка 9) не превосходит если применяется быстрый алгоритм объединения непересекающихся множеств. Остальная часть цикла, очевидно, занимает постоянное время, не зависящее от размера Засылка начальных данных в занимает время а в время где число узлов в