Деревья

1.

ДЕРЕВЬЯ
ПРЕПОДАВАТЕЛЬ
ПРОФ. ИВАНИЛОВА
Т.Н

2.

Деревья
Деревом называется граф G, если он является
связным и не имеет циклов.
Следующие утверждения эквивалентны:
1. Граф G – дерево;
2. Граф G является связным и число его ребер на
единицу меньше числа его вершин;

3.

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

4.

Остовное дерево (ОД) графа
Остовное дерево связного графа (псевдографа)
G – любой его подграф, содержащий все вершины
графа G и являющийся деревом.
Пусть G связный граф (псевдограф). Тогда
остовное дерево G должно содержать (n -1) ребер
(Св-во 2). Следовательно, для получения остовного
дерева графа G необходимо удалить из G (m-(n-1))
ребер. ν(G) = m-n+1 называется
цикломатическим числом связного графа G.

5.

Алгоритм выделения остовного
дерева для связного графа
Пусть задан граф G=(V,X). n вершин, m ребер G.
Шаг 1.Выбираем в G произвольную вершину u1, которая
образует подграф G1 графа G. i: = 1
Шаг 2.IF i = n, THEN конец алгоритма и Gi – искомое остовное
дерево графа G. ELSE
Шаг 3.Пусть построено дерево Gi, являющееся подграфом графа
G и содержащее вершины u1, u2, … , ui. Строим граф Gi+1,
добавляя к Gi новую вершину ui+1 V, смежную в G с некоторой
вершиной uj графа Gi и новое ребро {ui+1, uj}. Граф Gi+1 также
является деревом. i: = i+1 и переход к шагу 2.

6.

Минимальное остовное
дерево (МОД) графа
Пусть G – нагруженный граф.
Для ребра х задана функция l(x)–длина х.
МОД это ОД связного нагруженного
графа с минимальной суммой длин
ребер.

7.

Алгоритм выделения МОД
Шаг 1.Выберем в графе G ребро минимальной длины. Вместе с
инцидентными ему вершинами оно образует подграф G2 графа G.
i:= 2.
Шаг 2.IF i = n, THEN конец алгоритма . Gi искомое МОД графа G.
ELSE
Шаг 3.Строим граф Gi+1, добавляя к графу Gi новое ребро
минимальной длины. Выбор осуществляется из ребер графа G.
Одна вершина Gi , другая - вершина графа G, не содержащаяся в
G i.
Вместе с этим ребром включаем в Gi+1 и инцидентную ему вершину,
не содержащуюся в Gi . i: = i+1, переходим к шагу 2.