Поиск маршрутов в графе. Алгоритм Терри

1.

Поиск маршрутов в графе

2.

Алгоритм Терри – это поиск
маршрута при обходе графа по
определенным правилам
Описание алгоритма:
Исходя из v, осуществлять последовательный переход
от каждой достигнутой вершины к смежной ей
вершине, руководствуясь следующими правилами:
1.
Идя по произвольному ребру, всякий раз отмечать
направление, по которому оно было пройдено;
2.
Исходя из v всегда следовать только по тому
ребру, которое не было пройдено, или было
пройдено в противоположном направлении;
3.
Исходя их всякого v, по первому заходящему в v
ребру, идти лишь тогда, когда нет других
возможностей.

3.

Условие задачи
Задан неориентированный граф G.
V1
V2
V4
V3
V5
Используя алгоритм Терри, определить замкнутый
маршрут, проходящий ровно по два раза (по
одному в каждом направлении) через каждое
ребро графа

4.

Начинаем движение с вершины
графа V1, единственная доступная
нам вершина - V2. Отмечаем
направление движения стрелкой.
- обозначение первого входящего в вершину
ребра.
V1
V2
V4
V3
V5

5.

Из вершины V2 движемся в любом
направлении, кроме того по которому
уже проходили. Выбираем V4.
V1
V2
V4
V3
V5

6.

Из вершины V4 движемся в любом
направлении, кроме того по
которому уже проходили. Выбираем
V3.
V1
V2
V4
V3
V5

7.

Из вершины V3 движемся в любом
направлении, кроме того по
которому уже проходили. Выбираем
V2.
V1
V2
V4
V3
V5

8.

Из вершины V2 движемся в любом
направлении, кроме того по
которому уже проходили. По правилу
3 идти в V1 нельзя. Выбираем V3.
V1
V2
V4
V3
V5

9.

Из вершины V3 движемся в любом
направлении, кроме того по
которому уже проходили. По правилу
3 идти в V4 нельзя. Выбираем V5.
V1
V2
V4
V3
V5

10.

Из вершины V5 движемся в любом
направлении, кроме того по
которому уже проходили. Выбираем
V4.
V1
V2
V4
V3
V5

11.

Из вершины V4 двигаться в V2 нельзя
(правило 3). Выбираем V5.
V1
V2
V4
V3
V5

12.

Из вершины V5 можем двигаться
только в V3.
V1
V2
V4
V3
V5

13.

Из вершины V3 можем двигаться
только в V4.
V1
V2
V4
V3
V5

14.

Из вершины V4 можем двигаться
только в V2.
V1
V2
V4
V3
V5

15.

Из вершины V2 можем двигаться
только в V1.
V1
V2
V4
V3
V5

16.

Маршрут, проходящий ровно по два раза
(по одному в каждом направлении) через
каждое ребро графа определен.