|
Алгоритм определения компонент двусвязности Анализ компонент двусвязности компьютерной сети показывает, насколько она устойчива при разрушениях отдельных узлов. Таким образом, если граф, образованный компьютерами сети, двусвязен, то сеть сохранит способность функционировать даже при выходе из строя одного из компьютеров. При планировании авиаперевозок двусвязность компоненты графа гарантирует возможность переправить пассажиров по другому маршруту при закрытии аэропорта по погодным условиям. Точками сочленения в связном графе служат такие вершины, удаление которых превращает граф в несвязный. Точки сочленения - это такие вершины, которые принадлежат сразу двум компонентам двусвязности. На рис. 1 это вершины D и H. Определение точек сочленения и компонент двусвязности тесно связаны между собой. 
Точки сочленения можно обнаружить с помощью грубой силы, удаляя из графа поочередно каждую вершину и пользуясь одним из наших алгоритмов обхода графа для проверки связности оставшейся части. Если оставшийся граф связен, то удаленная вершина не является точкой сочленения. При таком подходе мы должны выполнить N обходов графа с N вершинами, что потребует O(N2) операций. Однако сохраняя незначительное количество дополнительной информации при обходе графов, можно обнаружить все точки сочленения и компоненты двусвязности при единственном обходе. Рассмотрим пути в графе с рис. 1, начинающиеся в вершине F. Видно, что вне зависимости от порядка прохождения узлов всякий путь из F в любую из вершин A, B или C должен проходить через вершину D. Это означает, что вершина D является точкой сочленения, а подграф, включающий вершины A, B, C и D - компонентой двусвязности. Мы будем строить алгоритм на обходе графа в глубину. Из статьи "Алгоритмы обхода в глубину и по уровням" Вы можете узнать, что при обходе в глубину мы перебираем ребра, пока не встретится тупик. При попадании в тупик происходит возвращение вдоль пройденного пути, однако теперь мы потребуем, чтобы алгоритм сообщал информацию о том, насколько высоко мы окажемся в дереве обхода, если пойдем за тупик. Эти возвратные ребра в дереве обозначают циклы в графе. Все вершины цикла должны принадлежать одной компоненте двусвязности. Расположение возвратных ребер указывает, насколько далеко мы можем вернуться по дереву прежде, чем встретим точку сочленения. При реализации алгоритма будем подсчитывать число посещенных узлов графа. Каждому узлу сопоставим индекс - номер, указывающий момент посещения узла. Другими словами, первый посещенный узел будет иметь номер 1, второй - номер 2 и т.д. После попадания в тупик мы просмотрим все соседние с ним вершины (за исключением той, из которой только что пришли) и будем считать наименьший из номеров этих вершин индексом возврата из тупика. Если тупик соединен всего с одной вершиной (той самой, из которой мы только что пришли), то индексом возврата будем считать номер тупика. При возвращении в узел, который не является корнем дерева обхода, мы сравним его номер с возвращенным индексом возврата. Если индекс возврата не меньше номера текущего узла, то только что пройденное поддерево (за вычетом всех ранее найденных компонент двусвязности) является компонентой двусвязности. Всякая внутренняя вершина дерева обхода в глубину возвращает наименьшее значение среди всех индексов примыкающих вершин и всех возвращаемых ей индексов возврата. Как будет действовать эта процедура на нашем графе с рис. 1? Начав с вершины F, мы присвоим ей номер 1. Затем мы перейдем к вершинам D (номер 2), B (номер 3), A (номер 4) и C (номер 5). Вершина C является тупиком, и из нее идут ребра назад в вершины A, B и D. Номер вершины D является наименьшим, поэтому индекс возврата 2 будет возвращен в вершину A. Поскольку индекс возврата меньше номера вершины A, эта вершина не является точкой сочленения. Пока индекс 2 является наименьшим, и он будет возвращен также в вершину B. Процесс возвращения продолжается, пока мы не вернемся в вершину D и не обнаружим, что номер этой вершины совпадает с индексом возврата, а значит вершины A, B, C и D образуют компоненту двусвязности. Затем мы возвращаемся в корневую вершину F дерева обхода и переходим из нее в вершину E (с номером 6), за которой последуют вершины G (номер 7) и H (номер 8). Затем мы переходим к вершине I (номер 9), и, поскольку она тупиковая и к ней не примыкает никаких вершин, отличных от H, ее номер возвращается в качестве индекса возврата. Когда вершина H получает от вершины I индекс возврата 9, мы обнаруживаем еще одну компоненту двусвязности, содержащую вершины H и I. Теперь в вершине H сравниваются три значения: индекс 1 (задаваемый ребром возврата к вершине F), индекс 9 (возвращенный из вершины I) и индекс 8 (номер самой вершины H). Наименьший из этих индексов возвращается сначала в G, а затем в E. Затем вершина E возвращает полученное значение индекса возврата назад в корневую вершину, и, поскольку мы посетили уже все вершины графа, оставшиеся узлы D, E, F, G и H образуют еще одну, последнюю, компоненту двусвязности. На рис. 2 изображен результат выполнения этой процедуры, откуда видно, что точками сочленения в исходном графе служат вершины D и H - единственные вершины, входящие в различные компоненты двусвязности. 
|
