Алгоритмические задачи на графах

• Название: Алгоритмические задачи на графах
• Дата: 29.09.2021
• Размер: 1.07 Mb.
• Имя файла: Alg-graphs-full (1).pdf
• Тип: Учебное пособие; #238917
• страница: 3 из 12

1, T = ?
k i=1
T
i
. Пусть e = (v, w)  ребро наименьшей стоимости в E \ T такое, что его концы принадлежат разным деревьями. Тогда существует остовное дерево, содержащее все ребра из T и e, стоимость которого не больше стоимости любого остовного дерева для G, содержащего T Доказательство. Пусть S
0
= (V, T
0
)
 остовное дерево минимальной стоимости, содержащее все ребра T , и ребро e /? T
0
. Тогда в имеется некоторый путь p извне содержащий e
. Выберем на нем первое такое ребро e
0
= (v
0
, w
0
)
, для которого v
0
? V
i
, а w
0
/
? V
i
. Рассмотрим множество ребер T
0 1
= (T
0
? {e}) \ {e
0
}
. Это множество задает остовное дерево, так как добавление ребра e к приводит по лемме 4.1 к образованию единственного цикла, а удаление ребра этот цикл разрушает. Так как e
0
/
? T
, то выбор e гарантирует, что c(e) ? Поэтому c(T
0 1
) = c(T
0
) + c(e) ? c(e
0
) ? c(T
0
)
. Из выбора тогда следует, что c(T
0 1
) = c(T
0
)
и,
следовательно, S
1
= (V, T
0 является требуемым остовным деревом.

Эта лемма лежит в основе алгоритма построения минимального остовного дерева МинО- стов. Для ускорения в нем используются эффективные алгоритмы для реализации очередей с приоритетами (можно для этого выбрать, например, сортирующие деревья или деревья) и структуры данных и алгоритмы для представления системы множеств и выполнения операций
ОБЪЕДИНИТЬ-НАЙТИ (для этого можно выбрать, например, деревья со сжатием путей).
АЛГОРИТМ МинОстов
Вход: G = (V, E)- связный неориентированный граф, c(e) - функция стоимости ребер.
Выход: T - множество ребер минимального остовного дерева.
Структуры данных Q - очередь с приоритетами для ребер, V S - набор непересекающих- ся подмножеств вершин G, элементы V S - множества вершин остовных деревьев в текущем остовном лесу := ?; V S := создать очередь с приоритетами Q из всех ребер из E;
3.
FOR EACH v ? V DO добавить {v} к V S;
4.
WHILE |V S| > 1 DO
5.
{
(v, w) := M IN (УДАЛИТЬ, (v, w));
6.
W 1 НАЙТИ W 2 := НАЙТИ W 1 6= W 2 ОБЪЕДИНИТЬ 1, W 2, W 1); T := T ? {(v, Теорема 4.1. Алгоритм МинОстов строит минимальное остовное дерево для связного графа. Если в цикле в строках 4 - 9 рассматривается d ребер, то затрачивается время, где m = |E|. В худшем случае выполнение алгоритма МинОстов занимает время O(m Доказательство. Нетрудно проверить, что инвариантом цикла в строках 4-9 является следующее свойство

система множеств V S = {V
1
, . . . , и набор ребер T задают остовной лес {(V
1
, T
1
), (V
2
, T
2
),
. . . , (V
k

, исходного графа G, (T = ?
k i=1
T
i
)
, который может быть расширен до минимального остовного дерева графа Это свойство, очевидно выполнено перед началом цикла, т.к. каждое из деревьев в V содержит одну вершину, а множество ребер T пусто. Пусть оно выполнено перед очередным выполнением тела цикла. Если на этом выполнении для выбранного ребра (v, w) вершины v и оказываются в разных деревьях, то это ребро добавляется ка соответствующие деревья объединяются в стр. 8. Очевидно, циклы при таком объединении не появляются и система V остается остовным лесом для G. Так как ребро (v, w) имеет минимальный вес, то по лемме этот лес может быть расширен до минимального остовного дерева.
Из связности G следует, что после завершения МинОстов лес V S будет состоять из одного дерева и оно и будет минимальным.
Оценим время работы алгоритма МинОстов. Для операций с очередью ребер Q выберем,
например, двоичное сортирующее дерево. Тогда его инициализация в стр. 2 производится за время O(|E|), а каждая операция извлечения минимального ребра в стр. 5 выполняется за время. Для реализации системы множеств V S и операций ОБЪЕДИНИТЬ-НАЙТИ
над ними выберем деревья и алгоритмы со сжатием путей. Тогда стр. 3 выполняется за время, а все операции НАЙТИ и ОБЪЕДИНИТЬ в стр. 6 и 8  за время O(|V |G(|V где G(|V |) << log
2
|V |
 медленно растущая функция. Поэтому, если в основном цикле рассматривалось ребер, то стр. 5 выполнялась d рази общее время алгоритма не превосходит) + O(d log
2
|E|) + O(|V |G(|V |) = O(d log
2
|E|)
, так как d ? |V | ? Пример 8. Рассмотрим следующий нагруженный граф G
1
:
H
H
H
H
H
H
@
@
@
@
@
a a
a a
a a












H
H
H
H
H


















a b
c d
e f
g
5 1
6 2
12 7
4 3
15 Рис. 13: Граф Применим к нему алгоритм МинОстов. Для простоты сразу покажем порядок, в котором будут выдаваться ребра из очереди Q в стр алгоритма = {(a, g), (b, c), (g, e), (e, d), (a, b), (g, c), (d, g), (f, g), (e, f ), (c, d), (a, f Выполнение основного цикла представим в виде таблицы, каждая строка которой соответствует рассмотрению очередного ребра (v, w) в стр. 5. В столбце T ребра, включаемые в отмечены +. Вначале система V S состоит из семи множеств V
i
(i = 1, . . . , 7)
, содержащих по одной вершине

(v, w)
T
W1
W2
V
1
V
2
V
3
V
4
V
5
V
6
V
7
{a}
{b}
{c}
{d}
{e}
{f }
{g}
(a, g)
+
1 7
{a, g}
{b}
{c}
{d}
{e}
{f }
(b, c)
+
2 3
{a, g}
{b, c}
{d}
{e}
{f }
(g, e)
+
1 5
{a, e, g}
{b, c}
{d}
{f }
(e, d)
+
1 4
{a, d, e, g}
{b, c}
{f }
(a, b)
+
1 2
{a, b, c, d, e, g}
{f }
(g, c)
?
1 1
{a, b, c, d, e, g}
{f }
(d, g)
?
1 1
{a, b, c, d, e, g}
{f }
(f, g)
+
1 5
{a, b, c, d, e, f, Таким образом, мы построили для минимальный остов S = (V, T ), где T = {(a, g), (b, c),
(g, e), (e, d), (a, b), (f, g)}
. Его стоимость c(S) = 23.
H
H
H
H
H
H




H
H
H
H
H


















a b
c d
e f
g
5 1
2 4
3 Рис. 14: Минимальный остов S = (V, T ) для графа G
1 4.2 Задачи
Задача 4.1. Найти минимальное остовное дерево для неориентированного графа G = (V, где V = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
, v
7
, v
8
, v
9
}
, E = {(v
1
, v
2
, 18), (v
1
, v
3
, 2), (v
3
, v
2
, 4), (v
3
, v
4
, 6), (v
3
, v
5
, 8),
(v
4
, v
6
, 5), (v
5
, v
4
, 4), (v
6
, v
1
, 7), (v
6
, v
8
, 4), (v
6
, v
7
, 3), (v
7
, v
5
, 1), (v
7
, v
8
, 7), (v
8
, v
1
, 5), (v
8
, v
9
, 3), (v
9
, v
1
, третий параметр в скобках - стоимость ребра).
Задача 4.2. Пусть S = (V, T )  остовное дерево наименьшей стоимости, построенное алгоритмом МинОстов для нагруженного неориентированного графа G = (V, E) сверши- нами. Пусть c
1
? c
2
? . . . ? c n?1
 это последовательность длин ребер из T , упорядоченных по возрастанию. Пусть S'  произвольное остовное дерево для G с длинами ребер d
1
? d
2
? . . . ? d n?1
. Показать, что c i
? d для всех i : 1 ? i ? n ? Задача 4.3. Пусть e  ребро максимального веса в некотором цикле графа G = (V, E). Докажите, что существует минимальный остов графа G
0
= (V, E \ {e})
, который является также минимальным остовом графа Задача 4.4. Пусть задано минимальное остовное дерево S = (V, T ) графа G = (V, E) и новое ребро (u, v) веса d, добавляемое к G. Предложите алгоритм сложности O(|V |), который строит минимальное остовное дерево графа G
1
= (V, E ? {(u, v)}).
26

Задача 4.5. Предложите эффективный алгоритм для построения "минимального"остовного дерева для неориентированного взвешенного графа G = (V, E) с весовой функцией c : E ? если "весом"дерева S = (V, T ) считать вес самого тяжелого ребра S, c(S) = max{c(e)|e ? T Задача 4.6. Алгоритм Прима (1957) для построения минимального остова отличается от алгоритма Крускала тем, что вместо очереди ребер Q поддерживает очередь с приоритетами для вершин QV . Приоритетом вершины в ней является минимальная длина ребра,
соединяющего данную вершину с вершиной уже построенного дерева. Алгоритм начинает построение с произвольной вершины v
0
? и помещает ее в множество вершин дерева Остальные вершины помещаются в очередь QV . На каждом этапе алгоритма Прима из выбирается вершина v с минимальной длиной ребра (v, u) до вершины u ? V
T
. Эта вершина удаляется из QV и добавляется к V
T
, ее отцом в дереве становится u.
1) Напишите реализацию алгоритма Прима на псевдокоде) Докажите корректность алгоритма Прима) Докажите, что его можно реализовать так, чтобы общее время работы не превосходило:
а) O(|V при непосредственном поиске вершины б) O(|V | log
2
|V |+|E| log
2
|V при использовании двоичной кучи для реализации очереди с при- оритетами);
в) O(|V | log
2
|V | + при использовании фиббоначиевой кучи для реализации очереди с при- оритетами).
Задача 4.7. Алгоритм Борувки (1926) основан наследующем простом утверждении:
Для каждой вершины ребро наименьшего веса, инцидентное этой вершине, должно входить в минимальное остовное дерево. (Докажите это утверждение.)
Поэтому ребра из этого утверждения образуют остовной лес, состоящий из не более чем |V |/2 деревьев. Для каждого из этих деревьев T ребро наименьшего веса (v, w), такое что v ? T , а w /? T также должно входить в минимальное остовное дерево. Алгоритм
Борувки на первом этапе строит остовной лес из ребер наименьшего веса, инцидентных каждой вершине. Затем на очередном этапе к нему добавляюся ребра минимального веса,
торчащие"из каждого дерева. При этом число деревьев сокращается по крайней мере вдвое) Напишите реализацию алгоритма Борувки на псевдокоде) Докажите корректность алгоритма Борувки.
3) Докажите, что время его работы не превосходит O(|E| log
2
|V Алгоритмы обхода графов
5.1
Поиск в глубину на неориентированном графе и задача о лабиринте Задачу поиска выхода из лабиринта можно формализовать так лабиринт  это неориентированный граф, вершины которого представляют "перекрестки"лабиринта, а ребра  дорожки между соседними перекрестками. Одна или несколько вершин отмечены как выходы. Задача состоит в построении пути из некоторой исходной вершины в вершину-выход.
В этом разделе мы рассмотрим метод обхода всех вершин графа, называемый поиском в глубину. Его идею кратко можно описать так:
находясь в некоторой вершине v, идем из нее в произвольную еще не посещенную смежную вершину w, если такой вершины нетто возвращаемся в вершину, из которой мы пришли в v
27

Алгоритм поискав глубину
Вход: G = (V, E)  неориентированный граф, представленный списками смежностей: для каждой v ? V список L
v содержит перечень всех смежных с v вершин.
Выход: NUM[v]  массив с номерами вершин в порядке их прохождения и множество (древесных) ребер T ? E, по которым осуществляется обход.
Алгоритм ПОГ
1. T = {}; NOMER = 1;
2. для каждой вершины v ? V положим NUM[v] = 0 и пометим v как "новую. WHILE существует "новая"вершина v ? V
4.
DO ПОИСК(v);
Основную роль в этом алгоритме играет следующая рекурсивная процедура ПОИСК. пометить v как "старую. NUM[v] = NOMER; NOMER = NOMER + 1;
7. FOR EACH w ? L
v
DO
8. IF вершина w "новая. THEN
10.
{ T := T ? {(v, w)};
11.
ПОИСК(w)
12.
}
Теорема 5.1. Алгоритм ПОГ обходит (нумерует) все вершины неориентированного графа = (V, за время O(max(|V |, |E|)). Если G  связный граф, то S = (V, T )  это остов если граф G не является связным, то S = (V, T )  это остовной лес для G, те. объединение остовных деревьев для каждой из компонент связности Доказательство. Оценка времени следует из того, что процедура ПОИСК может вызываться для каждой вершины не более одного раза, а правильность является непосредственным следствием утверждения о работе процедуры ПОИСК.
Лемма 5.1. Пусть G
1
= (V
1
, E
1
)
 компонента связности графа G и v
1
? V
1
 первая вершина, для которой в стр. 4 вызывается процедура ПОИСК. Тогда а) в процессе выполнения этого вызова процедура ПОИСК будет вызвана один раз для любой вершины w ? б) после завершения этого вызова все вершины из V
1
"старые"и имеют номера от до NOMER + |V
1
| ? в) добавленные кво время этого вызова ребра образуют остовное дерево для Доказательство. Пункта) доказывается индукцией по расстоянию от до Если это расстояние равно 1, то w ? и рассматривается в цикле в стр. Если она в этот момент "старая то значит ПОИСК) уже вызывался. Если же w "новая тов стр происходит вызов ПОИСК(w).
Предположим теперь, что ПОИСК) вызывается для всех вершин u, находящихся на расстоянии от v
1
, и пусть вершина w ? находится на рсстоянии (k + 1) от v
1
. Тогда имеется путь длины (k + 1) от до w. Пусть u  это предпоследняя вершина на этом пути.
Тогда расстояние от до u равно k и по нашему предпроложению в некоторый момент выполняется вызов ПОИСК. Так как w ? L
u
, тов этом вызове вершина w в некоторый момент рассматривается в цикле в стр. Как и выше, если она в этот момент "старая то ПОИСК(w)
уже вызывался. Если же w еще "новая тов стр происходит вызов ПОИСК

Пункт (б) непосредственно следует из (а, а циклы в T отсутствуют, так как каждое добавляемое ребро ведет из "старой"вершины в "новую".
.
Дерево S = (V, T ), которое строится алгоритмом ПОГ, называется глубинным остовом или глубинным остовным деревом графа G. Ребра, попавшие в множество T , называются прямыми, а не попавшие в это множество ребра из множества (E \ T )  обратными. Каждое обратное ребро (v, w) соединяет вершину v с ее предком w в глубинном остове (см. задачу Поэтому в исходном графе G оно определяет цикл от w к v по ребрам дерева T , а затем обратно от v к w по ребру (v, w). Поэтому алгоритм ПОГ можно использовать для проверки наличия циклов в G. Ребро (v, w) не добавляется к T , те. является обратным, тогда и только тогда,
когда в стр вызова ПОИСК) обнаруживается, что вершина w старая. Поэтому, добавив в процедуру ПОИСК) последнюю строку. ELSE ПЕЧАТЬ (v, мы получим процедуру, которая в дополнение построению к глубинного остова графа будет распечатывать список всех обратных ребер. Если этот список не пуст, тов графе имеются циклы, иначе  нет.
Алгоритм поискав глубину часто используется как основа для различных алгоритмов обработки графов. Вместо строки 6, в котрой вершина v получает номер NUM(v), можно вставить вызов любой процедуры, обрабатывающей информацию, связанную с этой вершиной (например, для задачи о лабиринте это может быть проверка того, что v является выходом из лабиринта. И тогда полученный вариант алгоритма обеспечит обработку всех вершин графа.
Ниже мы рассмотрим несколько применений этого алгоритма.
Определение 15. Ребро (v, w) неориентированного графа G = (V, E) называется мостом, если при его удалении из E число связных компонент графа увеличивается, те. в графе (V, E \ {(v, связных компонент больше, чем в Из этого определения, в частности, следует, что ребро является мостом тогда и только тогда, когда оно не входит нив какой цикл (почему. Поиск в глубину позволяет находить все мосты графа. Во-первых, заметим, что любой мост (v, w) является ребром глубинного остова,
так как другого пути, связывающего v и w нет. Во-вторых, если это ребро ориентировано от кто в глубинном остове нет обратных ребер, соединяющих w и его потомки с предками w
. Это условие является и достаточным, так как, если таких ребер нетто удаление (v, нарушит связь между v и w и они окажутся в разных компонентах связности. Обозначим через
ВЕРХ(w) минимум из NUM[w] и наименьшего из номеров вершин, к которым ведут обратные ребра от вершин поддерева T
w
. Тогда, учитывая, что обратные ребра соединяют потомков с предками и что номера предков меньше номеров потомков, предложенный критерий можно переформулировать в следующем виде.
Теорема 5.2. Ребро (v, w) глубинного остова D = (V, E) неориентированного графа G = (V, является мостом G тогда и только тогда, когда ВЕРХ) > NUM[v] или, что эквивалентно, ВЕРХ) = Вычисление значения ВЕРХ) можно организовать в процессе обхода в глубину, используя следующее соотношение:
ВЕРХ(w) = ВЕРХ) | (w, z)? прямое ребро }?{NUM[u] | (w, u)?? обратное ребро Для этого достаточно в строку 6 алгоритма ПОГ добавить начальное присвоение
ВЕРХ(v) := в строке 11 приписать после ПОИСК) присвоение
ВЕРХ(v) := ВЕРХ, ВЕРХ

учитывающее прямые ребра, и добавить строку. ИНАЧЕ ВЕРХ) := ВЕРХ, для учета обратных ребер.
Зная значения ВЕРХ, нетрудно выявить все мосты, используя критерий из теоремы Пример 9. Применим алгоритм ПОГ к графу G
2
, изображенному наследующем рисунке l
l l
@
@
@
@
P
P
P
P
P
P
P
P
P
P
P
A
A
A
A
,
,
,
,
,
\
\
\
P
P
P
P
P
P
P
P
P
w w
w w
w w
w w
w w
w
1 2
3 4
5 6
7 8
9 10 Рис. 15: Граф Его представление в виде списков смежности имеет следующий вид 6, 2
L
7
: 6, 8
L
2
: 1, 9, 10, 3
L
8
: 6, 7
L
3
: 2, 5, 4
L
9
: 2, 10, 11
L
4
: 3, 5
L
10
: 2, 9, 11
L
5
: 2, 3, 4
L
11
: 9, 10
L
6
: 1, 7, Алгоритм ПОГ вызовет процедуру ПОИСК. Эта процедура рекурсивно вызовет ПОИСК(6)
и т.д. Вот структура всех получающихся вызовов процедуры ПОИСК:
ПОИСК(1) ? ПОИСК) ? ПОИСК) ? ПОИСК(8)
?
ПОИСК(2) ? ПОИСК) ? ПОИСК) ? ПОИСК(11)
?
ПОИСК(3) ? ПОИСК) ? ПОИСК(4)
Вначале идут "горизонтальные"вызовы, затем возвраты справа налево и вызовы "по вертикали. В результате вершины получат следующие номера, отражающие порядок их прохождения Ребра остова T , построенные в процессе обхода графа, показаны наследующем рисунке.
Стрелки указывают направление обхода.
В процессе построения этого дерева были определены следующие обратные ребра (8, 6), (10, 2),
(11, 9), (5, и (4, 3). Нетрудно проверить, что добавление любого из этих ребер к T приводит к образованию простого цикла

-





/
?
-
-
@
@
@
@
R
,
,
,
,
,
-
\
\
\
R

w w
w w
w w
w w
w w
w
1 2
3 4
5 6
7 8
9 10 Рис. 16: Остовное "глубинное"дерево T графа Используя расширенный вариант ПОГ с вычислением функции ВЕРХ, мы получим следующий результат :
1 2
3 4
5 6
7 8
9 10 11
N U M :
1 5
9 11 10 2
3 4
6 ВЕРХ : 1 5 5 9 5
2 2
2 5
5 Так как ВЕРХ) = NUM[2] = 5 и ВЕРХ) = NUM[6] = 2, то по теореме 5.2 мостами графа являются ребра (1, 2) и (1, 6) и других мостов у него нет.
5.2
Поиск в ширину на неориентированном графе
Идея алгоритма поискав ширину"состоит в том, чтобы, начав обход с некоторой вершины, в первую очередь посетить ее соседей, затем соседей соседей и т.д. Алгоритм поискав ширину
ПОШ отличается от алгоритма ПОГ только процедурой ПОИСКШ, в которой вместо стека,
реализующего рекурсивные вызовы в ПОИСК, используется очередь вершин Q.
procedure ПОИСКШ(v):
5. создать пустую очередь Q;
6. ДОБАВИТЬ, v); пометить v как "старую. WHILE Q 6= ? DO
8.
{
w НАЧАЛО УДАЛИТЬ, w);
9.
N U M [w] := N OM ER; N OM ER := N OM ER + 1;
10.
FOR EACH u ? L
w
DO
11.
IF вершина u "новая { ДОБАВИТЬ, пометить u как "старую" };
14.
T := T ? {(w, Следующее утверждение аналогично теореме 5.1 о свойствах поискав глубину.
Теорема 5.3. Алгоритм ПОШ обходит (нумерует) все вершины неориентированного графа = (V, за время O(max(|V |, |E|)). Если G  связный граф, то S = (V, T )  это остов G,
31

если граф G не является связным, то S = (V, T )  это остовной лес для G, те. объединение остовных деревьев для каждой из компонент связности Эта теорема является непосредственным следствием следующей леммы.
Лемма 5.2. Пусть G
1
= (V
1
, E
1
)
 компонента связности графа G и v
1
? V
1
 первая вершина, для которой в стр. 4 вызывается процедура ПОИСКШ(v
1
)
. Тогда а) в процессе выполнения этого вызова каждая вершина w ? попадет один разв очередь
Q
;
б) после завершения этого вызова все вершины из V
1
"старые"и имеют номера от до NOMER + |V
1
| ? в) добавленные кво время этого вызова ребра образуют остовное дерево для г) путь от до любой вершины w ? в дереве является кратчайшим (по числу ребер)
путем между ив графе Доказательство. Лемма доказывается непосредственной индукцией по расстоянию от до w
. Для доказательства пункта (г) предположим, что для каждой вершины u, находящейся на расстоянии k ? 0 отв графе G, путь вот до u имеет длину k. Если вершина w находится на расстоянии k + 1 от v
1
, то у нее есть соседи, находящиеся от на расстоянии k. Пусть u первая из этих вершин, попавшая (по индуктивному предположению) в очередь Q. Тогда в момент выбора u из Q вершина w еще новая ив добавится ребро (u, w). Следовательно,
длина пути от до w в будет равна k + 1, те. это будет кратчайший путь.
Из этой леммы непосредственно получаем
Следствие. Для связного графа G = (V, E) алгоритм ПОШ строит остовное дерево S =
(V, T )
, которое является деревом кратчайших путей из его корня вовсе остальные вершины.
Такие деревья иногда называют геодезическими.
Пример 10. Применим алгоритм ПОШ к графу из примера 9, изображенному на рис. Напомним его представление в виде списков смежности 6, 2
L
7
: 6, 8
L
2
: 1, 9, 10, 3
L
8
: 6, 7
L
3
: 2, 5, 4
L
9
: 2, 10, 11
L
4
: 3, 5
L
10
: 2, 9, 11
L
5
: 2, 3, 4
L
11
: 9, 10
L
6
: 1, 7, Тогда при обходе в ширину получается следующая нумерация вершин G
2
:
V :
1 2
3 4
5 6
7 8
9 10 11
N U M :
1 3
8 11 10 2
4 5
6 При этом обход происходит по дугам дерева T , изображенного наследующем рисунке.
5.3
Двусвязные компоненты неориентированных графов
Как мы отмечали выше, отсутствие мостов в графе означает невозможность разрушить представляемую им сеть связи за счет удаления одного ребра. Рассмотрим еще одно свойство графов- двусвязность, которое делает невозможным разрушение соответствующей сети связи за счет удаления одной вершины

-

J
J
J
J
J
^
?
A
A
A
A
U
-
-
A
A
A
A
U
w w
w w
w w
w w
w w
w
1 2
3 4
5 6
7 8
9 10 Рис. 17: Остов графа G
2
, построенный алгоритмом ПОШ
Определение 16. Неориентированный граф G = (V, E) называется двусвязным, если для любых трех его попарно различных вершин w, v и a существует путь между w и v, не проходящий через a. Вершина v называется точкой сочленения (шарниром, точкой раздела) графа, если для некоторой пары различных вершин x и y (не совпадающих с v) всякий путь между x и y проходит через Следствие. Связный граф является двусвязным тогда и только тогда, когда в нем нет точек сочленения.
Определение 17. Максимальный двусвязный подграф графа G называется его двусвязной компонентой (иногда такие подграфы называются блоками графа).
Заметим, что изолированные вершины и мосты являются двусвязными компонентами.
Содержательно, точки сочленения  это слабые"места связного графа. Например, если граф представляет некоторую сеть связи, то повреждение пункта связи, соответствующего точке сочленения, приведет к разрыву сети, те. невозможности пересылать сообщения по всей сети.
Лемма 5.3. Пусть G
i
= (V
i
, E
i
) (i = 1, ..., k)
- двусвязные компоненты графа G = (V, Тогда) граф G
i двусвязен (i = 1, ..., k) :
2) для любой пары i 6= j |V
i
? V
j
| ? 1
;
3) a  точка сочленения G ?? для некоторых i и j {a} = V
i
? Доказательство. Пункт (1) следует из определения) Если бы |V
i
? V
j
| ? то для любых трех попарно различных вершин w, v и a из V
i
? V
j имелся бы путь между w и v, не проходящий через a и, следовательно, эти вершины составляли бы одну двусвязную компоненту) Пусть a  точка сочленения G. Тогда существуют две вершины w и v, любой путь между которыми проходит через a. Рассмотрим произвольный такой путь w, . . . , w
0
, a, v
0
, . . . , v
. Пусть w
0
? V
i и v
0
? Тогда V
i
6= V
j и V
i
? V
j
= Обратно, пусть {a} = V
i
? V
j
. Тогда для любой пары вершин w ? V
i v ? V
j любой путь между ними проходит через a, те. a является точкой сочленения.
Следующее утверждение связывает точки сочленения с глубинным остовным деревом графа Лемма 5.4. Пусть G = (V, E) - связный неориентированный графа- глубинное остовное дерево. Вершина a является точкой сочленения G тогда и только тогда, когда) a  корень дерева S ион имеет более одного сына или) a  не корень и у него есть сын s такой, что между ними его потомками и предками a нет обратных ребер.
Доказательство. (1) Если a  корень дерева S и у него имеестя хотя бы два сына и то любой соединяющий их путь проходит через a и поэтому a является точкой сочленения Если же у a лишь один сын s
1
, то между двумя любыми вершинами w и v, имеющими путь,
проходящий через a, имеется путь, проходящий через и не включающий a. Следовательно,
в этом случае a не является точкой сочленения) Пусть a  не корень и у него есть сын s такой, что между ними его потомками и предками a нет обратных ребер. Тогда любой путь между отцом a и s проходит через a и,
следовательно, a является точкой сочленения.
Предположим, что для каждого сына s вершины a имеется ребро (u s
, v s
)
, соединяющее его или некоторого его потомка u с каким-нибудь предком v вершины a. Пусть между w и v имеется путь, проходящий через a. Тогда, если w не является потомком a в S, а v входит в поддерево T
s с корнем s -сыном a, то имеется путь изв корень S, оттуда в v s
, затем по ребру (v s
, u в T
s
, затем изв и, наконец изв. Если w и v являются потомками a в поддеревьях и разных сыновей и вершины a, то между ними существует путь w ? . . . ? s
1
? . . . ? u s
1
? v s
1
? . . . ? v s
2
? u s
2
? . . . ? s
2
? . . . ? v
. Во всех случаях эти путине проходят через a. Следовательно, a не является точкой сочленения.
Пусть NUM[v] - номер, присвоенный v алгоритмом ПОГ. Напомним определение функции
ВЕРХ[v]), которая использовалась при определении мостов:
ВЕРХ[v] = min{{NUM[v]}, {NUM[w] | существует такое обратное ребро (x, w), что x - потомок v