Построение графа наименьшей длины.

ЗАДАЧА. Дан неориентированный граф. Построить связный подграф, имеющий минимальную суммарную длину входящих в него ребер.

ДАНО. (I,D,G) – неориентированный граф;

L(i,j) – длина ребра [i,j];

НАЙТИ. (I,D,G) – неориентированный связный граф, для которого достигается

АЛГОРИТМ.

1. Строим самое короткое ребро. Если имеется несколько ребер одинаковой длины, выбираем любое из них.

2. Из оставшихся ребер выбираем самое короткое, которое в совокупности е уже имеющимися не образует циклов.

3. процесс продолжается до тех пор, пока не будут исчерпаны все ребра.

ПРИМЕР 3.9. Построить граф наименьшей длины.

 

2 3

 

3 4 2

5 2 2

5 2

3 3 4 3

 

2 4 1

 

РЕШЕНИЕ :

 

 

Получившийся граф

Дата добавления: 2014-01-20; Просмотров: 2028; Нарушение авторских прав?; Мы поможем в написании вашей работы!