Граф называется связным, если для любых двух его вершин v, w существует простая цепь из v в w.

Определение. Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v, w (из v и w).

 Определение. Орграф называется односторонне связным, если для любых его двух вершин, по крайней мере, одна достижима из другой.

 Определение. Если граф не является связным, то он называется несвязным.

Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа.

Будем говорить, что вершина v графа G - точка сочленения, если G-v содержит больше компонент, чем G. Аналогично, ребро e графа G - мост, если G-e содержит больше компонент, чем G.

Поиск точек сочленения.

 Опишем простой алгоритм нахождения всех точек сочленения связного графа, основанный на методе поиска в глубину.

 1. Выполняется обход графа методом поиска в глубину, при этом для всех вершин v вычисляются числа dfnum[v] равные номерам вершин при обходе в глубину. В сущности, эти числа фиксируют последовательность обхода вершин в прямом порядке вершин глубинного остовного дерева.

 2. Для каждой вершины v вычисляется число low[v], равное минимуму чисел dfnum потомков вершины v, включая и саму вершину v, и предков w вершины v, для которых существует обратное ребро (x, w), где x - потомок вершины v. Числа low[w] для всех вершин v вычисляются при обходе остовного дерева в обратном порядке, поэтому при вычислении low[v] для вершины v уже подсчитаны числа low[x] для всех потомков x вершины v. Следовательно, low[v] вычисляется как минимум следующих чисел:

 a) dfnum[v]

 b) dfnum[z], для всех вершин z, для которых существует обратное ребро (v, z)

 c) low[x] всех потомков x вершины v

 3. Теперь точки сочленения определяются следующим образом:

a) корень остовного дерева будет точкой сочленения тогда и только тогда, когда он имеет двух или более сыновей. Так как в остовном дереве, которое получается методом поиска вглубь, нет поперечных ребер, то удаление такого корня расчленит остовное дерево на отдельные поддеревья с корнями, яляющимися сыновьями корня построенного остовного дерева.

 b) вершина v, отличная от корня, будет точкой сочленения тогда и только тогда, когда имеет такого сына w, что low[w] >= dfnum[v]. В этом случае удаление вершины v (и, конечно, всех инцидентных ей ребер) отделит вершину w и всех ее потомков от остальной части графа. Если же low[w] < dfnum[v], то существует путь по ребрам дерева к потомкам вершины w и обратное ребро от какого-нибудь из этих потомков к истинному предку вершины v (именно значение dfnum для этого предка равно low[w]). Поэтому в данном случае удаление вершины v не отделит от графа поддерево с корнем w.

Поиск мостов.

 Рассмотрим ребро (u, v). Пусть вершина u была раньше при обходе в глубину, чем вершина v. Если low[u] равно low[v], то вершины u и v принадлежат одному простому циклу, а, значит, ребро (u, v) - не мост. Если low[u] не равно low[v], то тогда дополнительно рассмотрим номера вершин при обходе в глубину (т.е. dfnum[u] и dfnum[v]). Если low вершины равно ее номеру при обходе (т.е. dfnum[u] = low[u]), то тогда либо она была первая в цикле при обходе в глубину, либо она не принадлежит ни одному циклу. Если она не принадлежит ни одному из циклов, то тогда ребро (u, v) - мост. Осталось рассмотреть случай, когда обе эти вершины являются первыми в циклах при обходе. Пусть это так, тогда цикл вершины u, соединен c циклом вершины v ребром (u, v). Значит (u, v) - мост. В остальных случаях ребро (u, v) не является мостом.