Остовное дерево связного графа

Любой его подграф, содержащий все вершины графа Gи являющийся деревом (т.е. не содержит циклов и из одной вершины в другую можно попасть единственным путем). Определяется неоднозначно.

Компонента связности графа

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

Лес

Неориентированный граф без циклов (может быть и несвязным). Компонентами связности леса являются деревья (т.е. лес это тот же неориентированный граф, который может быть несвязным).

Сильно связный ориентированный граф (или сильный)

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

Односторонне связный ориентированный граф

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

Слабо связный ориентированный граф (или слабый)

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

Несвязный ориентированный граф

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

Компонента сильной связности в орграфе

Сильно связными компонентами орграфа называются его максимальные по включению сильно связные подграфы.

Алгоритм построения глубинного остовного леса:

Шаг 1. Выбираем в Gпроизвольную вершину u₁, которая образует подграф G_iлеса G, являющийся деревом.

Шаг 2. Если i= n, где n= n(G) (проверка на наличие всех вершин исходного леса в построенном остовном лесу), то задача решена, и G_i, искомый остовныйлеслесаG. В противном случае переходим к шагу 3.

Шаг 3. Пусть уже построено дерево G_i, являющееся подграфом лесаG и содержащее некоторые вершины u₁, ...u_i, где 1<i<n-1. Строим граф G_i+1, добавляя к деревуG_iновую вершину u_i+1, смежную в Gс некоторой вершиной u_j графа G_i, и новое ребро {u_i+1 , u_j}.Если такое ребро есть, то присваиваем i:=i+l и переходим к шагу 2. Если невозможно найти ребро, соединяющее вершину u_i+1с вершиной u_j (в силу возможной несвязности леса G), то переходим к шагу 4.

Шаг 4.Принимаем вершину u_j+1из шага 3 за начало нового дерева в лесу G, присваиваем i:=i+l и переходим к шагу 2.

Классификация ребер оргафа

1. Ребра деревьев—это ребра, входящие в лес поиска в глубину. На рис. 2 это ребра (1, 2), (2, 3), (2, 5), (3, 4).

 2. Обратные ребра—это ребра, соединяющие вершину с ее предкомв дереве поиска в глубину (ребра-циклы, возможные в ориентированных графах, считаютсяобратнымиребрами).Нарис. 2 эторебра (5, 1), (6, 6).

 3. Прямые ребра—это ребра, соединяющие вершину с ее потомком, но не входящие в лес поиска в глубину: (2, 4) на рис. 2.

 4. Перекрестные ребра—все остальные ребра графа.Онимогут соединять две вершины из одного дерева поиска в глубину, если ниодна их этих вершин не является предком другой, или же вершины из разных деревьев: (5, 4), (6, 1) на рис. 2.

Выделение компонент связности в неориентированном графе

Этап 1(первоначальная разметка):

Шаг 1.Пометить все вершины графа маркером «1»;

Шаг 2. Пометить любую вершину с маркером «1» маркером «2»;

Этап 2 (разметка соседних вершин):

Шаг 3. Если нет вершин, помеченных маркером «2» - переходим к этапу 3;

Шаг 4. Выбираем любую вершину с маркером «2», помечаем ее маркером «3», а все соседние вершины, помеченные маркером «1», помечаем маркером «2». Затем повторяем этот этап сначала;

Этап 3 (сбор результатов):

Шаг 5. Если нужно получить список вершин, входящих в одну компоненту связности с заданной вершиной, то выбираем вершины, помеченные третьим маркером;

Шаг 6. Если нужно получить список вершин, не входящих в одну компоненту связности с заданной вершиной, то выбираем вершины, помеченные маркером «1»;

Шаг 7.Если нужно просто проверить граф на связность, то считаем вершины, помеченные первым маркером, и сравниваем получившееся число с нулем. Если число вершин, помеченных первым маркером, равно нулю, то граф связный.

Выделение компонент сильной связности в орграфе

Этап 1(первоначальная разметка):

Шаг 1.Пометить все вершины графа маркером «1»;

Шаг 2. Пометить любую вершину с маркером «1» маркером «2»;

Этап 2 (разметка соседних вершин):

Шаг 3. Если нет вершин, помеченных маркером «2» и все вершины в графе помечены маркером «D_i» - переходим к этапу 3. Если нет вершин, помеченных маркером «2», но есть вершины с маркером «1» и без маркера «D_i», то i = i + 1 и переходим к шагу 2. Если есть вершина с маркером «2», переходим к шагу 4;

Шаг 4. Выбираем любую вершину vс маркером «2», помечаем ее маркером «3» и маркером «D_i»(если она еще не помечена маркером «D_i»)(здесь i - номер компоненты связности), а все соседние вершины u, достижимые из этой вершины и помеченные маркером «1», помечаем маркером «2». Если нет достижимых соседних вершин с маркером «1», то повторяем этап 2.

Шаг 5. Проверяем, есть ли путь из вершины uобратно в вершину v. Если есть – помечаем вершину uмаркерами «3» и «D_i». Если нет – снова помечаем вершину u маркером «1». Затем повторяем этот этап сначала;

Этап 3 (сбор результатов):

Шаг 6. Если нужно получить список вершин, входящих в одну компоненту связности с заданной вершиной, то выбираем вершины, помеченные соответствующим маркером «D_i»;

Шаг 7. Если нужно получить список вершин, не входящих в компоненту связности «D_i»то выбираем вершины, помеченные маркером, отличным от маркера «D_i»;

Таким образом, результатом данного алгоритма будут:

а) количество компонент сильной связности;

б) сгруппированные по компонентам связности вершины орграфа;