Элементы теории графов и их технические приложения - 23 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

23
1. Строим граф Т
1
=О
n
+е
1
, присоединяя к пустому графу О
n
на множестве
вершин VG ребро е
1
∈EG минимального веса.
2.
Если граф Т
i
уже построен и i<n-1, то строим граф T
i+1
=T
i
+e
i+1
, где e
i+1
–
ребро графа G, имеющее минимальный вес среди ребер, не входящих в Т
i
и
не составляющих циклов с ребрами из Т
i
.
Можно доказать, что алгоритм Краскала всегда приводит к остову
минимального веса.
Пример
. Рассмотрим взвешенный граф, изображенный на рис. 31 (а).
Рис. 31
Построить для него остов минимального веса.
Решение.
Полагаем е
1
={1,4} – ребро минимального веса 1 (веса указаны рядом
с ребрами), е
2
={4,5}. Среди оставшихся ребер минимальный вес имеют два ребра
{1,5} и {2,3}. Однако первое не пригодно для построения, т.к. составляет цикл с
двумя предыдущими ребрами, поэтому берем е
3
={2,3} и добавляем к нему ребро
е
4
={2,5}. Итак, ребра {1,4}, {4,5}, {2,3}, {2,5} составляют остов минимального веса
(рис. 28 (б)).
Алгоритм Прима отличается от алгоритма Краскала тем, что на каждом этапе
строится не просто ациклический граф, но дерево.
1.
Выбираем ребро е
1
=аb минимального веса и строится дерево Т
1
, полагая
VT={ab}, ET={e
1
}.
2.
Если дерево T
i
порядка i+1 уже построено и i<n-1, то среди ребер,
соединяющих вершины этого дерева с вершинами графа G, не входящими
в Т
i
, выбираем ребро е
i+1
минимального веса. Строим дерево T
i+1
,
присоединяя к Т
i
ребро е
i+1
вместе с его не входящим в Т
i
концом.
Этот алгоритм также приводит к остову минимального веса.
В некоторых ситуациях требуется построить остов не минимального, а
максимального веса. К такой задаче также применимы алгоритмы Краскала и
Прима.
7. Полюсные графы
7.1. Физические системы с сосредоточенными компонентами.
Для физических систем, допускающих идеалированное представление в виде
схем с сосредоточенными компонентами широко используются структурные модели
в форме графов. Соединение между собой компонентов таких систем
осуществляется путем объединения их полюсов, образующих узлы схемы. В
зависимости от числа полюсов различают двухполюсные и многополюсные
компоненты, которые так и называют двухполюсниками и
многополюсниками.
Например, схема на рис. 32 представляет собой соединение двух трехполюсников
(А и В), четырехполюсника (С) и трех двухполюсников (Д, Е, F).

Страницы