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

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

) | i = 1, . . . , k} ?
S
k i=1
E
i
. Корнем этого дерева является вершина r
0 3) Других графов в классе D нет.
Рисунок 7 иллюстрирует это определение v
1) T
0
:
2) T :
m m
m t
t t






H
H
H
H
H
j







B
B
B
B
B
B
B







B
B
B
B
B
B
B
T
1
T
k r
0
r
1
r Рис. 7: Индуктивное определение ориентированных деревьев
Теорема 3.2. Определения ориентированных деревьев 11 и 12 эквивалентны.
Доказательство. ? Пусть граф G = (V, E) удовлетворяет условиям определения 11. Покажем индукцией по числу вершин |V |, что G ? Если |V | = 1, то единственная вершина v ? V является по свойству (1) корнем дерева, те. в этом графе ребер нет E = ?. Тогда G = T
0
? Предположим, что всякий граф с ? n вершинами, удовлетворяющий определению 11 входит в D. Пусть граф G = (V, E) с (n + й вершиной удовлетворяет условиям определения 11. По условию (1) в нем имеется вершина-корень r
0
. Пусть из выходит k ребер и они ведут в вершины r
1
, . . . , r k
(k ? 1)
. Обозначим через G
i
, (i = 1, . . . , граф, включающий вершины {v ? V | v достижима из r и соединяющие их ребра E
i
? E
. Легко понять, что G
i удовлетворяет условиям условиям определения 11. Действительно, вне входят ребра, т.е.
эта вершина  корень G
i
. В каждую из остальных вершин из V
i входит по одному ребру как ив. Если v ? V
i
, то она достижима из корня r по определению графа G
i
. Так как |V
i
| ? то по индуктивному предположению G
i
? D
. Тогда граф G получен по индуктивному правилу) определения 12 из деревьев G
1
, . . . , G
k и поэтому принадлежит классу Если некоторый граф G = (V, E) входит в класс D, то выполнение условий (1)-(3) определения для него легко установить индукцией по определению 11. Предоставляем это читателю

в качестве упражнения.
С ориентированными деревьями связана богатая терминология, пришедшая из двух источников ботаники и области семейных отношений.
Корень  это единственная вершина, в которую не входят ребра, листья  это вершины,
из которых не выходят ребра. Путь из корня в лист называется ветвью дерева. Высота дерева это максимальная из длин его ветвей. Глубина вершины  это длина пути из корня в эту вершину. Для вершины v ? V , подграф дерева T = (V, E), включающий все достижимые из v вершины и соединяющие их ребра из E, образует поддерево T
v дерева T с корнем v (см. задачу. Высота вершины v  это высота дерева T
v
. Граф, являющийся объединением нескольких непересекающихся деревьев, называется лесом.
Если из вершины v ведет ребро в вершину w, то v называется отцом или родителем w, а w
 сыном или ребенком v (в последнее время в англоязычной литературе чаще употребляется асексуальная пара терминов родитель  ребенок. Из определения дерева непосредственно следует, что у каждой вершины кроме корня имеется единственный отец. Если из вершины v ведет путь в вершину w, то v называется предком w, а w  потомком v. Вершины, у которых общий отец, называются братьями или сестрами.
Определим важный подкласс ориентированных деревев  бинарные или двоичные деревья.
Определение 13. Ориентированное дерево называется бинарным или двоичным, если у каждой его внутренней вершины имеется не более двух сыновей, причем ребра, ведущие к ним помечены двумя разными метками (обычно используются метки из пар левый  правый  1, +  ? и т.п.)
Бинарное дерево называется полным, если у каждой его внутренней вершины имеется два сына и все его ветви имеют одинаковую длину.
Несложно подсчитать число листьев и вершину полных бинарных деревьев.
Лемма 3.2. Полное бинарное дерево высоты h содержит 2
h листьев и (2
h+1
? 1)
вершин.
Выделим еще один класс графов, обобщающий ориентированные деревья, ориентированные ациклические графы. У этих графов может быть несколько корней  вершин, в которые не входят ребра, ив каждую вершину может входить несколько ребер, а не одно, как у деревьев Представления деревьев
Поскольку дерево  это частный случай графа, то каждое из рассмотренных в разделе 2 представлений графов является также и представлением деревьев. Кроме этого можно определить несколько специальных представлений деревьев Сылка на вершину-отца
В некоторых задачах, использующих деревья, требуется перемещаться по дереву только от вершин-потомков к вершинам-предкам. В этом случае дерево T с n вершинами v
1
, . . . , v можно задать с помощью массива ОТЕЦ, в котором элемент ОТЕЦ является номером вершины,
являющейся отцом вершины v i
. Признаком корня может быть значение 0 в этом массиве Скобочное представление
Дерево  двумерный"объект. Но его можно представить в виде линейной строки, если использовать подходящую скобочную структуру. Определим скобочное представление СП(T ) дерева
T,
следуя индуктивному определению 12 ориентированного дерева

Базис. Если T = ({v}, ?)  дерево из одной вершины v, то СП(T ) = Индукционный шаг. Если дерево T получено по пункту (2) определения 12 путем присоединения деревьев T
1
, . . . , T
k к новому корню r, то СП(T ) = r(СП(T
1
), . . . ,
СП(T
k
)).
Пример 3. Например, cкобочное представление дерева G
2
, показанного на рис. 6, имеет вид
СП(G
2
) = c(a, (d(e(f ), g, h(k)), Ясно, что по скобочному представлению СП(T ) исходное дерево T восстанавливается однозначно. Обратное справедливо с точностью до порядка сыновей каждой вершины. Если такой порядок зафиксирован, то соответствующее ему представление единственно Представление множеством путей
Множество всех путей, начинающихся в корне дерева, очевидно, однозначно задает его структуру. Хотя такое представление является избыточным (например, все пути до внутренних вершин можно восстановить по путям до листьев, оно используется на практике при представлении иерархической структуры документов и книг в их содержаниях и оглавлениях.
Пример 4. Для дерева G
2
, показанного на рис. 6, такое представление имеет вид c.a c.d c.d.e c.d.e.f c.d.g c.d.h c.d.h.k c.b
3.2.4 Стандартное представление бинарного дерева
Из каждой внутренней вершины бинарного дерева выходит не более двух дуг  одна ведет клевому сыну, другая  к правому. Стандартным представлением бинарного дерева является списковая структура, состоящая из элементов-записей типа
ВЕРШИНА = (Номер, ЛЕВ, ПРАВ),
где ЛЕВ  это ссылка на левого сына вершины, а ПРАВ  на правого. Такая структура позволяет эффективно переходить от вершин-предков к вершинам-потомкам. Если в задаче нужно также передвигаться по дереву в обратном направлении, тов запись можно добавить поле
ОТЕЦ, указывающее на вершину-отца данной вершины Представление бинарного дерева с помощью массива
Для полных и близких к ним бинарных деревьев T = ({v
1
, . . . , v n
}, эффективным является представление с помощью одного целочисленного массива A[1..N], определяемого следующим образом корень дерева T , A[2i]  левый сын вершины A[i], A[2i + 1]  правый сын вершины Если соответствующего сына нетто значение равно 0. Это представление позволяет легко перемещаться по дереву сверху вниз и снизу вверх, используя умножение и деление на 2. Размер
N
массива A, представляющего дерево высоты h равен Поэтому для редких деревьев или деревьев, у которых одна ветвь которых намного длиннее других, это представление неэффективно

3.2.6 Представление произвольного дерева с помощью бинарного
Произвольное дерево можно представить с помощью бинарного дерева с сохранением числа вершин и дуг. Мы определим индуктивно такое представление Bin(T
1
, . . . , для леса деревьев, Базис. Если n = 1 и T
1
= ({v}, ?)
 дерево из одной вершины v, то Bin(T
1
) = Индукционный шаг. Если дерево получено по пункту (2) определения 12 путем присоединения деревьев T
11
, . . . , T
1k к новому корню r, то Bin(T
1
, . . . , имеет корень r, левым сыном этого корня при k > 0 является корень бинарного дерева Bin(T
11
, . . . , T
1k
)
, а правым сыном при n > 1 является корень бинарного дерева Bin(T
2
, . . . , Пример 5. Применив эти реккурентные соотношения к дереву показанному на рис. получим бинарное дерево показанное наследующем рисунке m
m m
m m
m m
m m
b h
d g
e f
c Рис. 8: Бинарное представление дерева с рис. Достаточно неочевидное рекурсивное правило, определяющее Bin(T ), можно просто переформулировать в виде локального правила, определяющего левого и правого сыновей каждой вершины в Bin(T ) левым сыном вершины v является ее первый сын в T, а правым сыном правый брат в в T. Это правило однозначно определяет Bin(T ) для упорядоченного дерева с фиксированным порядком сыновей каждой вершины Деревья и формулы (выражения)
Напомним общее понятие формулы над системой функций B. Аналогичные синтаксические объекты в логике предикатов назваются термами, а в языках программирования такие конструкции часто называются выражениями.
Итак, формула надмножеством функций F, множеством констант C и множеством переменных определяется индуктивно последующим правилам.
•
Переменная из Var есть формула.
•
Константа из C есть формула.
•
Если g
1
, . . . , g k
 формулы, а f
(k)
 местная функция из F, то f(g
1
, . . . , g k
)
 это формула

Обозначим множество всех таких формул через F(F, C, Рассмотрим класс упорядоченных размеченных деревьев T (F, C, Var), листья которых помечены элементами из (C ? Var), а внутренние вершины  функциями из F, причем, если вершина помечена символом местной функции из F, то у нее имеется k сыновей x
1)x ? Var ? T
x
:
m c
c ? C
?
T
c
:
2) ? = f k
(g
1
, . . . , g и g i
? T
i с корнем r i
T
?
:
m m
m t
t t






H
H
H
H
H
j
1
k







B
B
B
B
B
B
B







B
B
B
B
B
B
B
T
1
T
k f
r
1
r Рис. 9: Индуктивное определение связи между формулами и деревьями
Предложение 3.1. Между множеством формул F(F, C, Var) и множеством деревьев (F, C, имеется взаимно однозначное соответствие.
Доказательство. Это соответствие легко устанавливается индукцией по определениям формул и деревьев. Оно показано выше на рис. Пример 6. Рассмотрим, например, класс обычных арифметических формул надмножеством функций F = {+, ?, ?, :}, целочисленных констант C = {0, 1, 2, . . .} и переменных = {x, y, z, . . Пусть формула ? = +(?(5, +(x, 7)), (: (y, +(x, 7))) (ее обычное представление) Тогда в соответствии с предложением 3.1 эта формула представляется деревом T
?
, изображенном на рис. 10.
i







)
P
P
P
P
P
P
P
q i
@
@
@
R
i
@
@
@
R
i i




H
H
H
j i
i




H
H
H
j
+
v
1
*
v
2
:
v
3 5
v
4
+
v
5
y v
6
+
v
7
x v
8 7
v
9
x v
10 Рис. 10: Дерево На этом рисунке не указаны явно номера ребер, выходящих из внутренних вершин дерева, которые идентифицируют порядок аргументов операций. Предполагается, что для коммутативных операций +, * это несущественно, а для некоммутативных, таких, как :, первый аргумент расположен левее второго

Заметим, что у деревьев, представляющих арифметические или логические (булевские)
формулы, внутренние вершины имеют не более х сыновей, те. они являются бинарными.
Ориентированные ациклические графы также используются для представления формул.
Они получаются из соответствующих деревьев при склеивании вершин, представляющих одинаковые подформулы. Для формулы ? = 5 ? (x + 7) + y : (x + 7) такой граф получается при склеивании вершин и дерева T
?
, представляющих подформулу (x + 7).
m









)
P
P
P
P
P
P
P
P
P
q m
@
@
@
@
R
m
1
m m





H
H
H
H
j













)
2
m m
m
+
v
1
*
v
2
:
v
3 5
v
4
+
v
5
y v
6
x v
8 Рис. 11: Ациклический граф На этом рисунке явно указаны номера ребер, выходящих из вершины v
3
, которые определяют порядок аргументов приписанной этой вершине операции :. Ясно, что при отсутствии такого указания и использовании порядка по умолчанию  первый аргумент слева  граф представлял бы другое выражение Обходы деревьев
Часто при обработке представленной в дереве информации требуется обойти некоторым регулярным способом все его вершины. Имеется два естественных стандартных способа обхода деревьев. Каждый из них позволяет линейно упорядочить вершины дерева и тем самым представить его двумерную структуру в виде линейной последовательности вершин.
Прямой (префиксный) обход дерева основан на принципе сначала родитель, затем дети.
Определим индукцией по построению дерева T в определении 12 его прямое представление
ПР(T ) следующим образом) Если T
0
= ({v}, ?)
, то ПР) = v.
2) Если T получено из деревьев T
1
, . . . , T
k и нового корня по пункту (2) определения то ПР ) = ПР) . . .
ПР(T
k
).
Обратный (суффиксный) обход дерева основан на противоположном принципе сначала дети, затем родитель. Вот его индуктивное определение) Если T
0
= ({v}, ?)
, то ОБР(T
0
) = v.
2) Если T получено из деревьев T
1
, . . . , T
k и нового корня по пункту (2) определения то ОБР(T ) = ОБР(T
1
) . . .
ОБР(T
k
) Для бинарных деревьев, внутренние вершины которых имеют не более х сыновей, помеченных как левый и правый, можно естественно определить еще один способ обхода инфиксный (внутренний) обход, основанный на принципе сначала левый сын, затем родитель,
а затем правый сын. Он определяется следующим образом) Если T
0
= ({v}, ?)
, то ИНФ(T
0
) = v.
19

2) Если T получено из деревьев T
1
, и нового корня по пункту (2) определения 12, то
ИНФ(T ) = ИНФ(T
1
)r
0
ИНФ(T
2
).
(Если одно из деревьев T
1
, пусто, то соответствующее ему инфиксное представление тоже пусто).
Пример 7. Построим в соответствии с этими определениями три разных обхода бинарного дерева T
?
, изображенного на рис. 10 (в скобках после вершины указана ее метка).
ПР(T
?
) = v
1
(+)v
2
(?)v
4
(5)v
5
(+)v
8
(x)v
9
(7)v
3
(:)v
6
(y)v
7
(+)v
10
(x)v
11
(7)
ОБР(T
?
) = v
4
(5)v
8
(x)v
9
(7)v
5
(+)v
2
(?)v
6
(y)v
10
(x)v
11
(7)v
7
(+)v
3
(:)v
1
(+)
ИНФ(T
?
) = Для упорядоченного размеченного дерева T из класса T (F, C, Var) по любому из указанных обходов ПР ), ОБР(T ) и, если дерево бинарное,  ИНФ(T ) можно однозначно восстановить само дерево T (см. задачу Замечание. Для вычислительных приложений особенно интересен обратный обход, иногда называемый обратной польской записью. За один проход по такой записи можно вычислить значение соответствующего выражения, используя стек, или откомпилировать его. Напомним правило вычисления по обратной записи движемся по ней слева направо, при прохождении констант или переменных вталкиваем их значения в стека при прохождении местной функции заменяем k верхних элементов стека назначение этой функции от них. В результате после завершения прохода по записи на стеке останется значение вычисляемого выражения.
Каждое из указанных рекурсивных определений обходов ПР, ОБР и ИНФ можно естественно преобразовать в рекурсивную процедуру на любом современном языке программирования.
Правильность таких процедур является непосредственным следствием их определений, но использование в реализации универсальных методов делает их зачастую менее эффективными,
чем соответствующие нерекурсивные процедуры. Мы приведем здесь нерекурсивную процедуру для построения инфиксного обхода бинарного дерева. Будем считать, что исходное дерево представлено стандартным способом каждая вершина  это элемент типа ВЕРШИНА = (Номер, ЛЕВ, ПРАВ. Доступ к дереву осуществляется через параметр КОРЕНЬ - ссылку на его корень. В алгоритме будет использоваться стек вершин S со стандартными операциями U SH(S, v)
 поместить (ссылку на вершину v наверх стека S, P OP (S)  удалить верхний элемент стека, T OP (S)  функция, возвращающая верх стека S и EMT Y (S)  предикат,
определяющий пустоту стека S. Переменная CUR будет указывать на текущую вершину в обходе, целочисленная переменная NOMER будет содержать номер текущей вершины. Результат алгоритма  массив NUM, в котором для каждой вершины v указан ее номер в инфиксном порядке Алгоритм ИНФ
1. CUR := КОРЕНЬ NOMER := 1;
2. PUSH(S,CUR); CUR := CUR. ЛЕВ. WHILE (CUR 6= NIL) or NOT EMPTY(S) DO
4.
{WHILE (CUR 6= NIL) DO
5.
{ PUSH(S,CUR); CUR := CUR. ЛЕВ := TOP(S); POP(S);
7.
NUM[CUR] :=NOMER; NOMER := NOMER+1;
8.
CUR := CUR. ПРАВ

Теорема 3.3. Алгоритм ИНФ строит инфиксный обход бинарного дерева T = (V, E) с n вершинами за время Доказательство. Если дерево T состоит из одной вершины, тов стр. 2 она будет помещена в стек S, в стр. 6  удалена из него, в стр. 7 получит номер 1, после чего алгоритм завершится,
так как S будет пуст.
Для дерева T с числом вершин n > 1 доказательство правильности ИНФ проведем индукцией по номеру t вершины в инфиксном порядке. Именно, покажем, что номер 1 ИНФ дается верно и что из предположения о том, что номер t присваивается верно, можно вывести, что и номер t + 1 также присваивается верно. Нам потребуется более сильное индуктивное предположение, в котором используется одно вспомогательное понятие. Левый путь из корня в вершину v  это подпоследовательность таких вершин v i
1
, . . . , v i
l на пути p = v
0
, v
1
, . . . , v k
= v из корня в v, у которых левые сыновья также находятся на Утверждение. Для каждого 1 ? t ? n ИНФ присваивает номер t в стр вершине верно ив этот момент в стеке S лежит левый путь в вершину Базис. Проверим, что номер t = 1 присваивается вершине, которая идет первой вин- фиксном порядке. Из определения этого порядка следует, что это самая левая вершина T, т.е.
последняя вершина на самом левом пути в дереве ( у нее нет левого сына. Алгоритм ИНФ
в стр. 2 поместит в S корень, затем в цикле в стр. 4-5 поместит в S самый левый путь в T, в стр. 6 сделает его последнюю вершину текущей и уберет из S, а в стр. 7 присвоит ей номер В этот момент в в стеке S будет лежать левый путь в Шаг индукции. Предположим, что для некоторого t ? 1 Утверждение выполнено. Покажем,
что оно будет выполнено и для t + Пусть номер t получила вершина v. Какая вершина w должна следовать зав инфиксном порядке Возможны три случая) Уесть правый сын v
0
. Тогда w  это самая левая вершина в поддереве с корнем она является первой в инфиксной нумерации этого поддерева (см. рис. 12 слева).
В этом случае алгоритм ИНФ в стр. 8 сделает вершину текущей, затем в цикле в стр. добавит в S эту вершину и самый левый путь из нее в w. После этого в стр. 6 CUR получит значение w, w покинет стеки в стр. 7 ей присвоится правильный номер t + 1. В этот момент в в стеке S будет лежать левый путь в CUR=w.
w v
1
v k
v v
0
m m
m m
m
H
H
H
j








qq qq qq qq qq qq qq qq qq qq qq q
m m
m m
m w
v
1
v k
v v
0




A
A
U
A
A
U
qq qq qq qq qq qq qq qq qq qq qq Случай Случай Рис. 12: Инфиксный порядок на вершинах вершина w непосредственно после v
2) У v нет правого сына, но левый путь из корня в v непуст. Тогда из определения инфиксного порядка следует, что w  это последняя вершина на левом пути из корня в v (см. рис. справа

В этом случае по предположению индукции в момент присвоения номера t вершине v наверху стека S лежит w. Алгоритм ИНФ в стр. 8 присвоит CUR значение NIL, вернется к началу основного цикла, пропустит цикл в стр. 4-5, в стр CUR получит значение вершины стека w,
w покинет стеки в стр. 7 ей присвоится правильный номер t + 1. Как ив предыдущем случаев этот момент в в стеке S будет лежать левый путь в CUR=w.
3) У v нет правого сына и левый путь из корня в v пуст. Это означает, что v  последняя вершина на самом правом пути в T иона является последней вершиной в инфиксном порядке.
В этом случаев момент присвоения номера вершине v стек S пуст. Алгоритм ИНФ в стр. присвоит CUR значение NIL вернется к началу основного цикла, не войдет в него, так как оба его условия ложны, и завершит работу.
Для оценки времени заметим, что каждая вершина может получить номер в стр. 7 и попасть в стек в стр. 5 не более одного раза. Отсюда следует, что общее время работы алгоритма
ИНФ не превосходит В стандартном представлении бинарных деревьев поля ЛЕВ и ПРАВ у вершин, не имеющих соответствующих сыновей содержат не несущее полезной информации значение 0 (или. На самом деле эти поля можно использовать для организации эффективного инфиксного обхода дерева без применения стека. Для этого в них можно хранить ссылки на соседей данной вершины в инфиксном порядке. При этом добавляются битовые поля-признаки для определения типа информации в полях ЛЕВ и ПРАВ. Получаемое представление называется прошитым представлением бинарного дерева. Вершины являются элементами типа
ВЕРШИНАП = (Номер, ЛЕВ, ПрЛев, ПРАВ, ПрПрав).
При этом, если вершина имеет левого сына, то ПрЛев=1 и поле ЛЕВ содержит ссылку на левого сына, а если у вершины левого сына нетто ПрЛев=0 и поле ЛЕВ содержит ссылку на вершину, предшествующую данной в инфиксном порядке. Аналогично, если вершина имеет правого сына, то ПрПрав=1 и поле ПРАВ содержит ссылку на правого сына, а если у вершины правого сына нетто ПрПрав=0 и поле ПРАВ содержит ссылку на вершину, следующую заданной в инфиксном порядке Задачи
Задача 3.1. Докажите, что если в связном неориентированном графе число вершин равно числу ребер, то можно выбросить одно из ребер так, что после этого граф станет деревом.
Задача 3.2. Пусть G = (V, E)  неориентированное дерево и v ? V  произвольная вершина. Докажите, что если для каждого ребра (u, w) ? E выбрать ориентацию от u к w, если им заканчивается путь изв, и ориентацию от w к u, если им заканчивается путь изв, то полученный ориентированный граф будет ориентированным деревом с корнем Используйте это утверждение для доказательства следующего факта если в неориентированном дереве G = (V, E) имеется вершина степени d > 1, тов нем имеется по крайней мере вершин степени Задача 3.3. Пусть T = (V, E)  это ориентированное дерево с корнем v
0
? V
. определим для каждой вершины v ? V подграф T
v
= (V
v
, следующим образом V
v
 это множество вершин, достижимых изв, а E
v
 это множество ребер из E, оба конца которых входят в V
v
. Доказать, что а) T
v является деревом с корнем б) если две разные вершины v и u имеют одинаковую глубину, то деревья T
v и T
u не пересе- каются.
Задача 3.4. Пусть G = (V, E)  ориентированный граф с n > 1 вершинами. Докажите,
что G является (ориентированным) деревом тогда и только тогда, когда в G нет циклов

имеется одна вершина r, в которую не входят ребра, а в каждую из остальных вершин v ? V \ входит ровно одно ребро.
Задача 3.5. Пусть корень ориентированного дерева T имеет 5 сыновей, а каждая из остальных внутренних вершин имеет три или четыре сына, при этом число вершин с я сыновьями вдвое больше числа вершин с я. Сколько всего вершин и ребер в T, если известно, что число его листьев равно Задача 3.6. Докажите по индукции, что в любом бинарном дереве число вершин степени на единицу меньше числа листьев.
Задача 3.7. Постройте дерево, представляющее следующую логическую формулу = ((X ? ¬Y ) ? ¬(Z ? (X ? Y ))) ? (¬Z + Y Для полученного дерева определите прямой, обратный и инфиксный обходы.
Задача 3.8. Постройте дерево и ациклический ориентированный граф, представляющие следующую арифметическую формулу = (a + b)/(c + a ? d) + ((c + a ? d) ? (a + b) ? (c ? Сколько вершин удалось сократить?
Задача 3.9. Для каждого из обходов деревьев ПР ), ОБР(T ) и ИНФ(T ) предложите процедуру, восстановления соответствующего дерева T ? T (F, C, Задача 3.10. Предложите нерекурсивные алгоритмы для прямого и обратного обхода деревьев (необязательно бинарных. Оцените их сложность.
Задача 3.11. Реализуйте процедуру, не использующую стек, для инфиксного обхода бинарного дерева, заданного прошитым представлением. Оцените ее сложность.
4
Минимальное остовное дерево
Пусть G = (V, E)  связный неориентированный граф. Если |E| > |V |?1, тов имеются циклы
(см. теорему 3.1). Тогда можно, удаляя лишние ребра, можно получить дерево, связывающее те же вершины. Такое дерево называется остовом графа Определение 14. Остовом (остовным деревом, каркасом, скелетом) связного неориентированного графа G = (V, E) называется дерево S = (V, T ) такое, что T ? Пусть задана функция c : E ? R, приписывающая каждому ребру e ? E его стоимость
(вес, длину) c(e) ? R (R  множество вещественных чисел. Тогда стоимость c(S) дерева определяется как сумма стоимостей всех его ребер, те. c(S) = Минимальным остовом называется остов минимальной стоимости.
Таким образом, минимальный остов  это самая дешевая (короткая) система путей, связывающая все вершины G. Его можно было бы найти, перебрав всевозможные остовы графа. Но этот перебор мог бы потребовать экспоненциального от числа ребер G времени. К счастью, задача определения минимального остова допускает эффективное решение с помощью жадных
алгоритмов.
4.1
Алгоритм Крускала
В этом пункте мы рассмотрим алгоритм построения минимального остова, который был предложен Крускалом в г. Два других эффективных алгоритма, принадлежащих Приму и
Борувке, описаны в задачах 4.6 и Следующая лемма является непосредственным следствием определения остовного дерева

Лемма 4.1. Пусть S = (V, T ) - остовное дерево для G. Тогда
(а) для любых двух вершин и из V путь между ив единственный;
(б) если к S добавить любое ребро из E \ T , то возникнет ровно один цикл.
Теоретическим обоснованием алгоритма Крускала является следующее утверждение.
Лемма 4.2. Пусть {(V
1
, T
1
), (V
2
, T
2
), . . . , (V
k
, T
k
)}
- произвольный остовной лес для G, k >