Мосты и точки сочленения
Мосты
Определение
Пусть дан неориентированный граф. Мостом называется такое ребро, удаление которого делает граф несвязным (или, точнее, увеличивает число компонент связности). Требуется найти все мосты в заданном графе.
Неформально, эта задача ставится следующим образом: требуется найти на карте такие дороги, при удалении которых пропадает путь между какими-либо двумя точками.
Суть алгоритма
Мы можем заметить тот факт, что ребро между точками v и u является мостом тогда и только тогда, когда из вершины u и её потомков нельзя вернуться в вершину v или подняться выше нее. Осталось лишь понять, как нам это выяснить.
Алгоритм
Разобьём ребра на ориентированные и будем хранить их в отдельной структуре. Пусть мы будем запоминать номер вершины, в которую направлено ребро, номер данного ребра (номер ребра равен номеру обратного ребра) и ссылку на его обратное ребро.
Заведём граф ссылок на рёбра и заполним его.
Запустим обход графа в глубину (DFS).
Будем для каждой вершины v хранить два значения:
Если встречаем вершину u, в которой еще не были, то спускаемся в неё и тогда dp[v] = min(dp[v], dp[u]). Тем самым проверяем опустились ли мы из вершины u и её потомков выше v.
Если встречаем вершину v, в которой уже были, то dp[v] = min(dp[v], d[u]). Тем самым проверяем не встретили ли мы вершину выше по обходу графа, чем вершина v.
По завершении обхода вершины v и её потомков:
Реализация
Задачи по теме
Точки сочленения
Определение
Точкой сочленения называется вершина, удаление которой делает граф несвязным.
Суть алгоритма
Мы можем заметить два факта:
Рассмотрим ребро между вершинами v и u. Тогда если из вершины u и ее потомков нельзя попасть в какого-либо предка вершины v и притом вершина v не является корнем дерева, то данная вершина и есть точка сочленения
Алгоритм
Заведем общий счетчик времени входа timer и два массива:
Запустим обход графа в глубину (DFS).
Если встречаем уже посещенную вершину u, то fup[v] = min(fup[v], tin[u]). Проверяем не спустились ли мы выше v.
По завершении обхода:
Точки сочленения (или обрезанные вершины) на графике
Вершина в неориентированном связном графе является точкой сочленения (или разрезанной вершиной), если ее удаление (и прорезание ребер через нее) разъединяет граф. Точки сочленения представляют собой уязвимости в подключенной сети — отдельные точки, отказ которых разделит сеть на 2 или более отключенных компонента. Они полезны для проектирования надежных сетей.
Для несвязанного неориентированного графа точка сочленения — это удаление вершины, которое увеличивает количество связанных компонентов.
Ниже приведены примеры графиков с точками сочленения, обведенными красным цветом. 
Как найти все точки сочленения в данном графе?
Простой подход состоит в том, чтобы один за другим удалить все вершины и посмотреть, вызывает ли удаление вершины несвязный граф. Ниже приведены шаги простого подхода для связного графа.
Временная сложность вышеуказанного метода составляет O (V * (V + E)) для графа, представленного с использованием списка смежности. Можем ли мы сделать лучше?
На следующем рисунке показаны те же точки, что и выше, с еще одной дополнительной точкой, что лист в дереве DFS никогда не может быть точкой сочленения.
Мы выполняем обход DFS данного графа с дополнительным кодом для определения точек сочленения (AP). При обходе DFS мы поддерживаем массив parent [], в котором parent [u] хранит родителя вершины u. Среди вышеупомянутых двух случаев первый случай прост для обнаружения. Для каждой вершины считайте детей. Если в настоящее время посещенная вершина u является корневой (parent [u] равен NIL) и имеет более двух дочерних элементов, выведите ее.
Как справиться со вторым случаем? Второй случай сложнее. Мы поддерживаем массив disc [] для хранения времени обнаружения вершин. Для каждого узла u нам нужно найти самую раннюю посещенную вершину (вершину с минимальным временем обнаружения), которая может быть достигнута из поддерева с корнем u. Поэтому мы поддерживаем дополнительный массив low [], который определяется следующим образом.
Далее следуют реализация алгоритма Тарьяна для нахождения точек артикуляции на C ++, Java и Python.
using namespace std;
// Класс, представляющий неориентированный граф
int V; // Количество вершин
list int > *adj; // Динамический массив списков смежности
void APUtil( int v, bool visited[], int disc[], int low[],
int parent[], bool ap[]);
Graph( int V); // Конструктор
void addEdge( int v, int w); // функция для добавления ребра на график
void AP(); // печатает точки сочленения
adj = new list int >[V];
void Graph::addEdge( int v, int w)
adj[w].push_back(v); // Примечание: график не ориентирован
void Graph::APUtil( int u, bool visited[], int disc[],
int low[], int parent[], bool ap[])
// Для простоты используется статическая переменная, мы можем избежать использования статической
// переменная путем передачи указателя.
static int time = 0;
// Количество детей в DFS Tree
// Пометить текущий узел как посещенный
// Инициализация времени обнаружения и низкого значения
disc[u] = low[u] = ++ time ;
// Проходим все вершины, прилегающие к этому
list int >::iterator i;
int v = *i; // v текущий соседний с вами
// Если v еще не посещено, то сделайте его дочерним для вас
// в дереве DFS и повторяем за ним
APUtil(v, visited, disc, low, parent, ap);
// Проверяем, имеет ли поддерево с корнем v соединение с
// один из предков тебя
low[u] = min(low[u], low[v]);
// (1) u является корнем дерева DFS и имеет двух или более детей.
if (parent[u] == NIL && children > 1)
// (2) Если u не является корнем и младшее значение одного из его дочерних элементов больше
// чем значение открытия для вас.
// Обновление низкого значения u для вызовов родительской функции.
low[u] = min(low[u], disc[v]);
// Функция для обхода DFS. Он использует рекурсивную функцию APUtil ()
// Пометить все вершины как не посещенные
bool *visited = new bool [V];
int *disc = new int [V];
int *low = new int [V];
int *parent = new int [V];
bool *ap = new bool [V]; // Для сохранения точек сочленения
// Инициализируем родительский и посещенный, и ap (точки артикуляции) массивы
// Вызываем рекурсивную вспомогательную функцию для поиска точек сочленения
// в дереве DFS с корнем из вершины ‘i’
if (visited[i] == false )
APUtil(i, visited, disc, low, parent, ap);
// Теперь ap [] содержит точки сочленения, печатаем их
// Программа драйвера для проверки вышеуказанной функции
// Создание графиков, приведенных на диаграммах выше
cout «\nArticulation points in first graph \n» ;
cout «\nArticulation points in second graph \n» ;
cout «\nArticulation points in third graph \n» ;
// Java-программа для поиска точек сочленения в неориентированном графе
// Этот класс представляет неориентированный граф, используя список смежности
// представление
private int V; // Количество вершин
// Массив списков для представления списка смежности
private LinkedList adj[];
adj = new LinkedList[v];
adj[i] = new LinkedList();
// Функция для добавления ребра в график
void addEdge( int v, int w)
adj[v].add(w); // Добавить w в список v.
adj[w].add(v); // Добавить v в список w
// Рекурсивная функция, которая находит точки сочленения с использованием DFS
void APUtil( int u, boolean visited[], int disc[],
int low[], int parent[], boolean ap[])
// Количество детей в DFS Tree
// Пометить текущий узел как посещенный
// Инициализация времени обнаружения и низкого значения
// Проходим все вершины, прилегающие к этому
Iterator i = adj[u].iterator();
int v = i.next(); // v текущий соседний с вами
// Если v еще не посещено, то сделайте его дочерним для вас
// в дереве DFS и повторяем за ним
APUtil(v, visited, disc, low, parent, ap);
// Проверяем, имеет ли поддерево с корнем v соединение с
// один из предков тебя
low[u] = Math.min(low[u], low[v]);
// (1) u является корнем дерева DFS и имеет двух или более детей.
if (parent[u] == NIL && children > 1 )
// (2) Если u не root и низкое значение одного из его потомков
// больше чем значение открытия для вас.
// Обновление низкого значения u для вызовов родительской функции.
low[u] = Math.min(low[u], disc[v]);
// Функция для обхода DFS. Он использует рекурсивную функцию APUtil ()
// Пометить все вершины как не посещенные
boolean visited[] = new boolean [V];
int disc[] = new int [V];
int low[] = new int [V];
int parent[] = new int [V];
boolean ap[] = new boolean [V]; // Для сохранения точек сочленения
// Инициализируем родительский и посещенный, и ap (точка артикуляции)
// Вызываем рекурсивную вспомогательную функцию для поиска артикуляции
// точки в дереве DFS с корнем из вершины ‘i’
if (visited[i] == false )
APUtil(i, visited, disc, low, parent, ap);
// Теперь ap [] содержит точки сочленения, печатаем их
public static void main(String args[])
// Создание графиков, приведенных на диаграммах выше
System.out.println( «Articulation points in first graph » );
Graph g1 = new Graph( 5 );
System.out.println( «Articulation points in Second graph» );
Graph g2 = new Graph( 4 );
System.out.println( «Articulation points in Third graph » );
Graph g3 = new Graph( 7 );
>
// Этот код предоставлен Aakash Hasija
# Программа Python для поиска точек сочленения в неориентированном графе
from collections import defaultdict
# Этот класс представляет неориентированный граф
#using представления списка смежности
# функция для добавления ребра на график
» ‘Рекурсивная функция, которая находит точки сочленения
используя обход DFS
# Количество детей в текущем узле
# Отметить текущий узел как посещенный и распечатать его
# Инициализировать время обнаружения и низкое значение
# Повторить для всех вершин, смежных с этой вершиной
# Если v еще не посещено, сделайте его потомком
# в дереве DFS и повторить его
if visited[v] = = False :
# Проверьте, подключено ли поддерево с корнем v
# один из предков тебя
low[u] = min (low[u], low[v])
# (1) u является корнем дерева DFS и имеет двух или более детей.
# (2) Если u не является корнем и низкое значение одного из его дочерних элементов больше
# чем значение открытия вас.
# Обновление низкого значения u для вызовов родительской функции
low[u] = min (low[u], disc[v])
# Функция для выполнения обхода DFS. Он использует рекурсивный APUtil ()
# Отметить все вершины как не посещенные
# и инициализировать родительский и посещенный,
Массивы # и ap (точка сочленения)
# Вызовите рекурсивную вспомогательную функцию
# найти точки сочленения
# в дереве DFS с корнем из вершины ‘i’
if visited[i] = = False :
for index, value in enumerate (ap):
if value = = True : print index,
# Создайте график, приведенный на диаграмме выше
print «\nArticulation points in first graph «
print «\nArticulation points in second graph «
print «\nArticulation points in third graph «
# Этот код предоставлен Ниламом Ядавом
Сложность времени: вышеупомянутая функция — простая DFS с дополнительными массивами. Таким образом, временная сложность такая же, как и у DFS, которая является O (V + E) для представления графа в списке смежности.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Точки сочленения, мосты и блоки
На рисунке v — точка сочленения, a w нет, х — мост, а y нет; отдельно приведены четыре блока графа G. Каждое ребро графа принадлежит точно одному из его блоков, так же как и каждая вершина, не являющаяся ни изолированной, ни точкой сочленения. Далее, ребра любого простого цикла графа G также принадлежат только одному блоку. Отсюда, в частности, следует, что блоки графа разбивают его ребра и простые циклы на множества, которые можно рассматривать как множества ребер. В первых трех теоремах этой главы устанавливаются несколько эквивалентных, условий, обеспечивающих существование у графа точки сочленения и моста и неразделимость графа.
Теорема. Пусть v — вершина связного графа G. Следующие утверждения эквивалентны:
(1) v — точка сочленения графа G;
(2) существуют такие вершины u и w, отличные от v, что v принадлежит любой простой (u-w)-цепи;
(3) существует разбиение множества вершин V— на такие два подмножества U и W, что для любых вершин u Î U и w Î W вершина v принадлежит любой простой (u-w)-цепи.
(3) влечет (2). Это немедленно следует из того, что (2) — частный случай утверждения (3).
Теорема. Пусть х — ребро связного графа G. Следующие утверждения эквивалентны:
(2) х не принадлежит ни одному простому циклу графа G;
(3) в G существуют такие вершины u и v, что ребро х принадлежит любой простой цепи, соединяющей u и v;
(4) существует разбиение множества V на такие подмножества U и W, что для любых вершин u Î U и w Î W ребро х принадлежит любой простой (u-w)-цепи.
Теорема. Пусть G — связный граф с не менее чем тремя вершинами. Следующие утверждения эквивалентны:
(2) любые две вершины графа G принадлежат некоторому общему простому циклу;
(3) любая вершина и любое ребро графа G принадлежат некоторому общему простому циклу;
(4) любые два ребра графа G принадлежат некоторому общему простому циклу;
(5) для любых двух вершин и любого ребра графа G существует простая цепь, соединяющая эти вершины и включающая данное ребро;
(6) для любых трех различных вершин графа G существует простая цепь, соединяющая две из них и проходящая через третью;
(7) для каждых трех различных вершин графа G существует простая цепь, соединяющая две из них и не проходящая через третью.
(3) влечет (4). Доказательство, как в предыдущем случае.
(7) влечет (1). Используя (7), получаем, что для любых двух вершин u и w ни одна из остальных вершин не может принадлежать каждой (u-w)-цепи. Следовательно, G должен быть блоком.
Теорема. В любом нетривиальном связном графе найдутся по крайней мере две вершины, не являющиеся точками сочленения.
Обходы графов
В этой статье рассмотрены основные применения обхода в глубину: топологическая сортировка, нахождение компонент сильной связности, решение задачи 2-SAT, нахождение мостов и точек сочленения, а также построение эйлерова пути и цикла в графе.
Поиск в глубину
Поиском в глубину (англ. depth-first search, DFS) называется рекурсивный алгоритм обхода дерева или графа, начинающий в корневой вершине (в случае графа её может быть выбрана произвольная вершина) и рекурсивно обходящий весь граф, посещая каждую вершину ровно один раз.
Как их заполнить: заведем таймер, отвечающий за «время» на текущем состоянии обхода, и будем инкрементировать его каждый раз, когда заходим в новую вершину:
У этих массивов много полезных свойств:
Эти свойства часто бывают полезными в задачах на деревья.
Мосты и точки сочленения
Определение. Мостом называется ребро, при удалении которого связный неориентированный граф становится несвязным.
Определение. Точкой сочленения называется врешина, при удалении которой связный неориентированный граф становится несвязным.
Пример задачи, где их интересно искать: дана топология сети (компьютеры и физические соединения между ними) и требуется установить все единые точки отказа — узлы и связи, без которых будут существовать два узла, между которыми не будет пути.
Наивный алгоритм поочередного удаления каждого ребра \((u, v)\) и проверки наличия пути \(u \leadsto v\) потребует \(O(m^2)\) операций. Чтобы научиться находить мосты быстрее, сначала сформулируем несколько утверждений, связанных с обходом в глубину.
Запустим DFS из произвольной вершины. Введем новые виды рёбер:
Прямые рёбра — те, по которым были переходы в dfs.
Обратные рёбра — то, по которым не было переходов в dfs.
Сооптимизировать его до линейного времени (до одного прохода dfs) поможет замечание о том, что обратные рёбра могут вести только «вверх» — к какому-то предку в дереве обхода графа, но не в другие «ветки» — иначе бы dfs увидел это ребро раньше, и оно было бы прямым, а не обратным.
\[ d_v = \min \begin
Точки сочленения
Задача поиска точек сочленения не сильно отличается от задачи поиска мостов.
Используя этот факт, можно оставить алгоритм практически прежним — нужно проверить этот критерий для всех прямых рёбер \(v \to u\) :
Единственный крайний случай — это корень, так как в него мы по определению войдём раньше других вершин. Но фикс здесь очень простой — достаточно посмотреть, было ли у него более одной ветви в обходе (если корень удалить, то эти поддеревья станут несвязными между собой).
Топологическая сортировка
Задача топологической сортировки графа звучит так: дан ориентированный граф, нужно упорядочить его вершины в массиве так, чтобы все графа рёбра вели из более ранней вершины в более позднюю.
Это может быть полезно, например, при планировании выполнения связанных задач: вам нужно одеться, в правильном порядке надев шорты (1), штаны (2), ботинки (3), подвернуть штаны (4) — как хипстеры — и завязать шнурки (5).
Во-первых, сразу заметим, что граф с циклом топологически отсортировать не получится — как ни располагай цикл в массиве, все время идти вправо по ребрам цикла не получится.
Во-вторых, верно обратное. Если цикла нет, то его обязательно можно топологически отсортировать — сейчас покажем, как.
Заметим, что вершину, из которой не ведет ни одно ребро, можно всегда поставить последней, а такая вершина в ациклическом графе всегда есть (иначе можно было бы идти по обратным рёбрам бесконечно). Из этого сразу следует конструктивное доказательство: будем итеративно класть в массив вершину, из которой ничего не ведет, и убирать ее из графа. После этого процесса массив надо будет развернуть.
Этот алгоритм проще реализовать, обратив внимание на времена выхода вершин в dfs. Вершина, из которой мы выйдем первой — та, у которой нет новых исходящих ребер. Дальше мы будем выходить только из тех вершин, которые если имеют исходящие ребра, то только в те вершины, из которых мы уже вышли.
Следовательно, достаточно просто выписать вершины в порядке выхода из dfs, а затем полученный список развернуть, и мы получим какую-то из корректных топологических сортировок.
Компоненты сильной связности
Мы только что научились топологически сортировать ациклические графы. А что же делать с циклическими графами? В них тоже иногда требуется найти какую-то структуру.
Для этого можно ввести понятие сильной связности.
Определение. Две вершины ориентированного графа связаны сильно (англ. strongly connected), если существует путь из одной в другую и наоборот. Иными словами, они обе лежат в каком-то цикле.
Понятно, что такое отношение транзитивно: если \(a\) и \(b\) сильно связны, и \(b\) и \(c\) сильно связны, то \(a\) и \(c\) тоже сильно связны. Поэтому все вершины распадаются на компоненты сильной связности — такое разбиение вершин, что внутри одной компоненты все вершины сильно связаны, а между вершинами разных компонент сильной связности нет.
Самый простой пример сильно-связной компоненты — это цикл. Но это может быть и полный граф, или сложное пересечение нескольких циклов.
Часто рассматривают граф, составленный из самих компонент сильной связности, а не индивидуальных вершин. Очевидно, такой граф уже будет ациклическим, и с ним проще работать. Задачу о сжатии каждой компоненты сильной связности в одну вершину называют конденсацией графа, и её решение мы сейчас опишем.
Если мы знаем, какие вершины лежат в каждой компоненте сильной связности, то построить граф конденсации несложно: дальше нужно лишь провести некоторые манипуляции со списками смежности. Поэтому сразу сведем исходную задачу к нахождению самих компонент.
Доказательство. Рассмотрим два случая, в зависимости от того, в какую из компонент dfs зайдёт первым.
После того, как мы сделали это с первой вершиной, мы можем пойти по топологически отсортированному списку дальше и делать то же самое с вершинами, для которых компоненту связности мы ещё не отметили.
Сортируем вершины в порядке убывания времени выхода.
Проходимся по массиву вершин в этом порядке, и для ещё непомеченных вершин запускаем dfs на транспонированном графе, помечающий все достижимые вершины номером новой компонентой связности.
После этого номера компонент связности будут топологически отсортированы.
Рассмотрим конъюнкцию дизъюнктов, то есть «И» от «ИЛИ» от каких-то перемений или их отрицаний. Например, такое выражение:
Если буквами: (А ИЛИ B) И (НЕ C ИЛИ D) И (НЕ A ИЛИ НЕ B).
Можно показать, что любую логическую формулу можно представить в таком виде.
Задача satisfiability (SAT) заключается в том, чтобы найти такие значения переменных, при которых выражение становится истинным, или сказать, что такого набора значений нет. Для примера выше такими значениями являются a=1, b=0, c=0, d=1 (убедитесь, что каждая скобка стала true ).
В случае произвольных формул эта задача быстро не решается. Мы же хотим решить её частный случай — когда у нас в каждой скобке ровно две переменные (2-SAT).
Затем построим граф импликаций: для каждой переменной в графе будет по две вершины, (обозначим их через \(x\) и \(!x\) ), а рёбра в этом графе будут соответствовать импликациям.
Оказывается, что это условие является не только достаточным, но и необходимым. Доказательством этого факта служит описанный ниже алгоритм.
Переформулируем данный критерий в терминах теории графов. Если из одной вершины достижима вторая и наоборот, то эти две вершины находятся в одной компоненте сильной связности. Тогда критерий существования решения звучит так: для того, чтобы задача 2-SAT имела решение, необходимо и достаточно, чтобы для любой переменной \(x\) вершины \(x\) и \(!x\) находились в разных компонентах сильной связности графа импликаций.
Пусть решение существует, и нам надо его найти. Заметим, что, несмотря на то, что решение существует, для некоторых переменных может выполняться, что из \(x\) достижимо \(!x\) или из \(!x\) достижимо \(x\) (но не одновременно). В таком случае выбор одного из значений переменной \(x\) будет приводить к противоречию, в то время как выбор другого — не будет. Научимся выбирать из двух значений то, которое не приводит к возникновению противоречий. Сразу заметим, что, выбрав какое-либо значение, мы должны запустить из него обход в глубину/ширину и пометить все значения, которые следуют из него, т.е. достижимы в графе импликаций. Соответственно, для уже помеченных вершин никакого выбора между \(x\) и \(!x\) делать не нужно, для них значение уже выбрано и зафиксировано. Нижеописанное правило применяется только к непомеченным ещё вершинам.
Итак, мы построили алгоритм, который находит искомые значения переменных в предположении, что для любой переменной \(x\) вершины \(x\) и \(!x\) находятся в разных компонентах сильной связности. Выше показали корректность этого алгоритма. Следовательно, мы одновременно доказали указанный выше критерий существования решения.
Эйлеров цикл
Определение. Эйлеров путь — это путь в графе, проходящий через все его рёбра.
Определение. Эйлеров цикл — это эйлеров путь, являющийся циклом.
Для простоты в обоих случаях будем считать, что граф неориентированный.
Также существует понятие гамильтонова пути и цикла — они посещают все вершины по разу, а не рёбра. Нахождение гамильтонова цикла (задача коммивояжера, англ. travelling salesman problem) — одна из самых известных NP-полных задач, в то время как нахождение эйлерового цика решается за линейное время — и мы сейчас покажем, как.
Теорема. Эйлеров цикл существует тогда и только тогда, когда степени всех вершин чётны.
Доказательство. Необходимость показывается так: можно просто взять эйлеров цикл и ориентировать все его ребра в порядке обхода. Тогда из каждой вершины будет выходить столько же рёбер, сколько входить, а значит степень у всех вершин исходного неориентированного графа была четной.
Достаточность докажем конструктивно — предъявим алгоритм нахождения.
Если условие на четность степеней вершин выполняется, то этот алгоритм действительно выводит эйлеров цикл, то есть последовательность из \((m+1)\) вершин, между соседними есть связи.
Следствие. Эйлеров путь существует тогда и только тогда, когда количество вершин с нечётными степенями не превосходит 2.
Кстати, аналогичная теорема есть и для ориентированного графа (можете сами попытаться сформулировать).
Доказать это можно например через лемму о рукопожатиях.
Как теперь мы будем решать задачу нахождения цикла в предположении, что он точно есть. Давайте запустимся из произвольной вершины, пройдем по любому ребру и удалим его.
Упражнение. Сформулируйте и докажите аналогичные утверждения для случая ориентированного графа.