Графы и сети. Харитонова Е.В. - 24 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

23
Теперь берем новую постоянную вершину С. Выполнение шага 2 не при-
водит к изменениям. Выполнив шаг 3, делаем вершину Е(7, В) постоянной. По-
лучает в результате рис. 1.53.
Рис. 1.53
Берем новую постоянную вершину Е и, используя шаг 2, меняем F(15, В)
на F(11, E). Выполнив шаг 3, делаем вершину F(11, Е) постоянной. Таким об-
разом, получаем рис. 1.54.
Рис. 1.54
Вершина F стала постоянной, поэтому процесс завершен и 11 – это крат-
чайшее расстояние от вершины A к вершине F. Если бы совокупность вершин
смежных с постоянной вершиной, была исчерпана до того, как мы достигли
вершину F, то задача не имела бы решения, поскольку бы не было бы пути от
вершины А
к вершине F. Для нахождения кратчайшего пути заметим, что вер-
шине F предшествует вершина Е, вершине Е предшествует вершина В, а вер-
шине В предшествует вершина А. Поэтому кратчайшим путем является АВЕF.
УПРАЖНЕНИЯ
I. Среди приведенных ниже графов найдите те, которые имеют эйлеров
цикл.
1.
а) б)
D(12, B)
7
10
2
4
B(5, A)
F(15, B)
E(7, B)
3
7
6
5
A(0, 0)
C(6, A)
2
D(12, B)
7
10
2
4
B(5, A)
F(11, E)
E(7, B)
3
7
6
5
A(0, 0)
C(6, A)
2
b
a c d e
ƒ h
g
i j
c
a e
i
g j
b d
f

Страницы