ВУЗ:
Составители:
Рубрика:
Эйлеров путь начинается в одной из вершин с нечетной степе-
нью и заканчивается в другой вершине с нечетной степенью.
Пояснение: Добавляем
вершину t и соединяем ее
с u и v. В новом графе
степени всех вершин чет-
ны и его эйлеровы циклы
находятся во взаимно од-
нозначном соответствии с
эйлеровыми путями ис-
ходного графа.
вершины
нечетной
степени
v
u
t
г
р
а
ф
G
Лекция 13. Нахождение пути наименьшей длины в графе.
Алгоритм Дейкстра.
Пусть G=<V,E> - орграф без петель, V={v
1
,…,v
n
}. Каждой дуге
<v
i
,v
j
> поставлено в соответствие некоторое действительное число
w
ij
, w
ij
≥ 0 , называемое весом (или длиной) дуги.
В реальной жизни вес дуги может означать стоимость проклад-
ки линий связи, например, между городами, обозначаемыми вер-
шинами графа, или длину дороги и т.д.
Если дуги <v
i
,v
j
> не существует, то w
ij
=
∞
. Матрица
(
)
n,j,i
ij
wW
1=
=
называется матрицей весов.
Пусть - путь в графе G. Тогда
- длина пути.
r
ii
v,...,v
1
rrr
iiiiii
w...w)v,...,v(d
1211 −
++=
Часто необходимо находить путь наименьшей длины (кратчай-
ший путь) в орграфе. Примером может служить следующая задача.
Задача.
Предположим, что вам необходимо иметь в своем рас-
поряжении автомобиль в течении нескольких лет. Имеется боль-
шой выбор автомобилей. Автомобили имеют различные сроки
эксплуатации и разную стоимость. Каким образом выбрать вари-
ант покупок автомобилей на заданном временном интервале
имеющий минимальную суммарную стоимость покупаемых авто-
мобилей?
Для того, чтобы свести данную задачу к графовой, представим
моменты времени возможных сделок на заданном временном ин-
50
Страницы
- « первая
- ‹ предыдущая
- …
- 48
- 49
- 50
- 51
- 52
- …
- следующая ›
- последняя »
