Деревья. Алгоритм Краскала

минимального остовного дерева

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

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

Длиной маршрута называется количество ребер в нем. Расстоянием между вершинами u, v (обозначается s(u,v)) называется наименьшая длина цепи < u,v >

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

Маршрут, в котором все ребра различны, называется цепью (путем)

содержащий циклов.
Дерево не имеет петель и кратных (параллельных) рёбер

(т.к кратные рёбра, инцидентные одним и тем же двум вершинам, образуют цикл).

дерева является мостом – при ее удалении граф распадается на

две части (два подграфа)

Для каждой пары вершин дерева (узлов) существует единственный маршрут, поэтому вершины удобно классифицировать по степени удаленности от корневой вершины.

Расстояние до корневой вершины V0 называется ярусом s вершины, s = d(V0,V).

Узел без поддеревьев называется листом и является висячей вершиной.

тогда, когда выполняется хотя бы одно из условий:
граф G(V,X

) связан и не содержит циклов;
граф G(V, X ) не содержит циклов и имеет n –1 ребро;
граф G(V, X ) связан и имеет n –1 ребро;
граф G(V, X ) не содержит циклов, но добавление ребра между несмежными вершинами приводит к появлению одного и только одного элементарного цикла;
граф G(V, X ) связный, но утрачивает это свойство после удаления любого ребра;
в графе G(V, X ) всякая пара вершин соединена цепью, и притом только одной.

Дерево с n вершинами имеет n –1 ребро, поэтому оно будет минимальным связным графом.

будет минимальным связным графом.

поддеревьев называется листом и является висячей вершиной.
Дерево, в котором

каждый узел либо является листом, либо образует два поддерева (левое и правое), называется бинарным

что для каждого элемента n все элементы в левом поддереве

будут меньше, чем n, а все элементы в правом поддереве - больше, чем n.

20, 10, 35, 15, 17, 27, 24, 8, 30

20

10

35

8

15

27

30

24

17

условия:
- Значение в любой вершине больше, чем значения ее

потомков.
- Все слои, кроме, может быть, последнего, заполнены полностью.
- Последний слой заполняется слева направо.

16, 11, 9, 10, 5, 6, 8, 1, 2, 4

16

11

9

10

5

6

8

4

1

2

если каждому его ребру поставлено в соответствие некоторое число (вес).
Взвешенными

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

единую компьютерную сеть. Для этого достаточно проложить (n-1) линий между

домами. Как соединить дома так, чтобы суммарная стоимость соединений (кабеля) была минимальна?

Остов графа (стягивающее дерево, spanning tree) – дерево, полученное из графа, выбрасыванием части ребер.

е сопоставлено некоторое число, называемое весом или длиной этой дуги.

Сумму весов дуг дерева в дальнейшем будем называть весом дерева или его множества дуг. Требуется найти такое остовное дерево Т, содержащего все вершины графа G, у которого вес был бы минимален. Такое дерево будет называться минимальным остовным деревом.

Суммарный вес равен
4 + 7 + 5 + 10 + 11 = 37

пока это возможно, проводится следующая операция:
из всех рѐбер, добавление

которых к уже имеющемуся множеству не вызовет появление в нѐм цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству.

Когда таких рѐбер больше нет, алгоритм завершѐн. Подграф данного графа, содержащий все его вершины и найденное множество рѐбер, является его остовным деревом минимального веса

весом
ребро создаст цикл?
добавить ребро в остовное дерево
еще есть ребра?
нет
да
да

выбирается ребро AD
Теперь наименьший вес, равный 5, имеет ребро CE.

Так как добавление CE не образует цикла, то выбираем его в качестве второго ребра

AB и BE с весом 7. Произвольно выбирается ребро AB,

выделенное на рисунке.
Ребро BD (выделено красным) ВЫБИРАТЬ ЗАПРЕЩЕНО, так как будет образован цикл ABD

ЗАПРЕЩЕНО:
(выделено красным)
BC - создаст цикл BCE,
DE - создаст цикл

DEBA,
FE - сформирует цикл FEBAD.

Алгоритм завершается добавлением ребра EG с весом 9. Минимальное остовное дерево построено.

деревьев.
4. Что называется бинарным деревом?
5. Что называется цикломатическим

числом графа? Чему равно это число в дереве? Лесе?
6. Какой граф называется сетью?
7. Что называется весом или длиной дуги?
8. Дайте определение остов графа.
9. Дайте определение минимальный остов графа.
10. В чем смысл алгоритма Краскала?