Page 24 - 4336

Контуром називається шлях, початок v і кінець v якого
n
0
збігаються. Контур називається циклом, якщо він представлений

ланцюгом, і простим циклом – якщо простим ланцюгом.

Приклад 1.8. Для графа, зображеного на рис. 1.10 б,

наведемо приклади можливих шляхів:

1) v v v v v v v – орієнтований маршрут;
0 1 3 2 1 3 4
2) v v v v v v – орієнтований ланцюг;
0 3 2 1 3 4
3) v v v v v v – орієнтований простий ланцюг
0 1 3 2 4 5
4) v v v v v v v v v – контур;
0 1 3 2 1 3 4 5 0
5) v v v v v v v v –цикл;
0 3 2 1 3 4 5 0
6) v v v v v – простий цикл.
0 3 4 5 0

1.4.3 Властивості маршрутів

1. Будь-який маршрут, що веде з вершини v у вершину w

(v≠w), містить простий ланцюг, що веде з v у w.

2. Будь-який найкоротший маршрут, що веде з вершини v у

вершину w (v≠w), є простим ланцюгом.

3. Довільний цикл містить простий цикл.

4. Якщо в графі для деяких трьох різних вершин v, u та w є

ланцюги, один з яких веде з v в u, а другий – з u в w, то існує

простий ланцюг, що веде з v у w.

5. Якщо в нетривіальному замкненому маршруті всі сусідні

ребра різні, то він містить цикл.

24