Эквивалентные определения дерева

End.

V:=t;

Begin write(t);

End.

Путь минимального веса в графе. Алгоритм Флойда

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

Существует много модификаций и методов решения этой задачи, зависящих от свойств графа (ориентированный или неориентированный, есть ли в нем контуры и т.д.), так и от свойств весов (неотрицательные или произвольные и т.д.). Одной из самых популярных является задача поиска кратчайших путей между всеми парами вершин. Для ее решения найден весьма эффективный алгоритм, созданный Уоршаллом и Флойдом.

Идея алгоритма следующая. Пусть граф имеет n вершин. Обозначим a_ij – расстояние между вершинами v_i и v_j (a_ij = r( v_i, v_j), если v_i и v_j смежны и a_ij = +¥ в противном случае); – длина кратчайшего пути из v_i в v_j с промежуточными вершинами в множестве { v₁, v₂ , …, v_k }. Имеем следующие равенства:

Первое равенство очевидно. Чтобы обосновать второе уравнение, рассмотрим кратчайший путь из v_i в v_j с промежуточными вершинами из множестве { v₁, v₂ , …, v_k, v_k+1}. Если этот путь не содержит v_k+1, то , иначе, деля путь из v_i в v_j на отрезки от v_i до v_k+1 и от v_k+1 до v_j, получим второе равенство. Заменяя во втором уравнении k + 1 на k, изменяющееся от 1 до n, и убирая верхние индексы, получим следующий алгоритм.

begin for i:=1 to n do

for j:=1 to n do D[i,j] := A[i,j];

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

D[i,j]:=min( D[i,j], D[i,k]+D[k,j] );

Зная матрицу D[i, j] кратчайших расстояний между всеми парами вершин, несложно построить сам кратчайший путь между двумя заданными вершинами s и t. Предлагается следующий алгоритм, определяющий путь с его конца.

while v <> s do

for u:=1 to n do

if( D[s,v] = D[s,u]+A[u,v] ) and (u<>v) then

begin write(u); v:=u; break; end;

Вычислительная сложность алгоритма Флойда равна, очевидно, О(n³), т.к. необходимо выполнить тройной цикл от 1 до n.

Тема 4. Деревья

Деревья – это графы специального вида. Они весьма широко используются во многих отраслях знаний и, в частности, в информационных технологиях – методах поиска информации, хранения данных, сортировке и мн. др.

Существует несколько определений дерева.

1) Связный граф с n вершинами и n – 1 ребрами.

2) Связный граф без циклов.

3) Граф, в котором каждая пара вершин соединена точно одной цепью.

Докажем эквивалентность этих определений.

1) Þ 2). Докажем, что в связном графе с n вершинами и n – 1 ребрами нет циклов. Предположим противное, т.е. цикл есть и e = (u, v) – ребро этого цикла. Удалим это ребро. Тогда граф останется связным, т.к. из u в v можно добраться по другой половинке цикла. В графе G\e n вершин, n – 2 ребер и он связан, т.е. у него 1 компонента связности, k = 1. По 3-й теореме о связности должно быть m = n – 2 ³ n – 1 – противоречие. Следовательно, циклов нет.

2) Þ 3). Хотя бы одна цепь, соединяющая u и v должна быть, т.к. граф связный. Предположим, что цепей не одна, а хотя бы две. Тогда, по свойству 3 маршрута, из них можно составить цикл – противоречие, т.е. 2-й цепи нет.

3) Þ 1). Из 3) следует, что граф связный. Так как каждая пара вершин соединена точно одной цепью, то удаление любого ребра увеличит на 1 число компонент связности. Пусть в графе m ребер. По 3-й теореме о связности должно быть m ³ n – 1. Удалив 1 ребро, получим m – 1³ n – 2, т.к. станет k = 2. Удалив 2 ребра, получим k = 3 и m – 2³ n – 3, и т.д. Удалим n – 1 ребер, получим k = n и m – (n – 1)³ n – n. Но, т.к. k = n, то ребер больше нет. Следовательно, они были удалены за n – 1 шагов, поэтому m = n – 1, ЧТД.

Задание 1. Пусть Т – дерево, Т₁, Т₂ – его поддеревья. Доказать, что – тоже дерево.

Задание 2. В дереве n > 1. Доказать, что имеется по крайней мере 2 висячих вершины.