1.4.Стягивающие деревья (каркасы)

Деревом называется произвольный неориентированный связный граф без циклов. Для произвольного связного неориентированного графа G = <V, E> каждое дерево <V, T>, где , будем назвать стягивающим деревом (каркасом или остовом) графа G. Ребра такого дерева являются ветвями, а все остальные ребра графа – хордами (очевидно это имеет смысл в контексте фиксированного стягивающего дерева). Следует отметить, что каждое дерево с n вершинами имеет n-1 ребер. Этот факт можно просто доказать, применяя индукцию относительно n.

Процедуры поиска в глубину и в ширину можно простым способом использовать для нахождения стягивающих деревьев. В обоих случаях достижение новой вершины u из вершины v вызывает включение в дерево ребра {v,u}.

WGD = proc (v:int; g:graph; НОВЫЙ:array of bool; T:stack)

modifies НОВЫЙ, T

effects 1. НОВЫЙ [v] = false

2. c = graph.fetch(g,v); i = circ.size(c)

3. пока i > 0

3.1. j = circ.element(c)

3.2. если НОВЫЙ[j], то

3.2.1. stack.pop(T,v); stack.pop(T,j)

3.2.2. WGD(j,g,НОВЫЙ,T)

иначе circ.change(c)

3.3. i = i-1

Рис.1.14.Процедура поиска в глубину в сочетании с нахождением ребра дерева.

Frame1 = proc(g:graph; r:int) returns(T:stack)

effects 1. для i = 1 до n НОВЫЙ[i] = true

2. T = stack.new( )

3. WGD(r,g,НОВЫЙ,T)

Рис.1.15.Процедура нахождения стягивающего дерева связного графа методом поиска в глубину.

На рис.1.16 представлены результаты определения стягивающих деревьев для графа, представленного на рис.1.1.б в общем виде и на рис.1.5.а в виде «массива» кольцевых структур, начиная от 1-ой (рис.1.16.а) и 6-ой вершин (рис.1.16.б).

Каждое стягивающее дерево, построенное алгоритмом Frame1, обладает следующим свойством. Назовем вершину r, с которой начинается поиск в графе, корнем стягивающего дерева . Очевидно, что в дереве существует только один путь от произвольной вершины к корню.

Для двух различных вершин v и u дерева будем считать, что u является потомком вершины v, если v лежит на пути (в дереве ) из u в корень. Если при этом имеет место v-u, то u – сын вершины v, v – отец вершины u.

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

Frame2 = proc (g:graph; r:int) returns (T:stack)

effects 1. для i = 1 до n НОВЫЙ[i] = true

2. T = stack.new

3. q = intqueue.new

4. intqueue.append(q,r)

5. НОВЫЙ[r] = false

6. пока not(intqueue.isempty(q))

6.1. v = intqueue.remfirst(q)

6.2. c = graph.fetch(g,v); i = circ.size(c)

6.3. пока i > 0

6.3.1. u = circ.element(c)

6.3.2. если НОВЫЙ[u], то

6.3.2.1. intqueue.append(q,u)

6.3.2.2. НОВЫЙ[u] = false

6.3.2.3. stack.pop(T,v)

6.3.2.4. stack.pop(T,u)

6.3.3. circ.change(c)

6.3.4. i = i - 1

Рис.1.17.Процедура нахождения стягивающего дерева связного графа методом поиска в ширину.

На рис.1.18 представлены результаты определения стягивающих деревьев для графа, представленного на рис.1.1.б в общем виде и на рис.1.5.а в виде «массива» кольцевых структур, начиная от 1-ой (рис.1.18.а) и 6-ой вершин (рис.1.18.б).

Построение стягивающего дерева с помощью процедуры Frame2 обеспечивает следующее свойство. Пусть - стягивающее дерево связного графа , построенное при помощи Frame2. Тогда путь в из произвольной вершины v до корня r является к ратчайшим путем из v в r в графе G.