Page 32 - 4386

Приклад 3.1. Визначити можливі маршрути та їхню

довжину з вершини v у v в графі, зображеному на рис. 3.1 а.
0
8

а б

Рисунок 3.1 – Приклади маршрутів

Розв'язок.

З вершини v в v ведуть, наприклад, наступні маршрути:
8
0
1) v v v - довжини 2;
0 3 8
2) v v v v v - довжини 4;
0 1 2 3 8
3) v v v v v - довжини 4;
7 8
0 3 4
4) v v v v v v v - довжини 6;
0 3 4 5 6 7 8
5) v v v v v v v - довжини 6;
0 3 4 5 4 7 8
6) v v v v v v v - довжини 6;
0 1 2 3 4 7 8
7) v v v v v v v v v - довжини 8;
0 1 2 3 4 5 6 7 8
8) v v v v v v v v v v v - довжини 10.
0 1 2 3 4 7 6 5 4 3 8
Маршрути 1 – 4, 6 та 7 є простими ланцюгами.

Маршрут, у якому збігаються початок і кінець (v та v )
n
0
називається циклічним. Циклічний маршрут називається циклом,

якщо він представлений ланцюгом, і простим циклом, якщо він

представлений простим ланцюгом.

Наприклад, маршрут v v v v v для графа, зображеного на
0 1 2 3 0
рис. 3.1 а, є простим циклом; маршрут v v v v v v v є циклічним
3 4 5 6 7 4 3
маршрутом; маршрут v v v v v v v v v є циклом, але не простим.
0 1 2 3 4 7 8 3 0

31