Page 34 - 4386

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

приведемо приклади орієнтованих маршрутів з вершини v до
0
вершини v :
6
1) v v v v ; v v v v ; v v v v - довжини 3;
0 2 5 6
0 4 3 6
0 1 3 6
2) v v v v v v - довжини 5.
0 2 5 4 3 6

а б

Рисунок 3.2

Орієнтованим ланцюгом називається шлях, кожна дуга

якого зустрічається не більше одного разу, а простим

орієнтованим ланцюгом – шлях, кожна вершина якого

зустрічається не більше одного разу.

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

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

Приклад 3.4. Для графа, зображеного на рис. 3.2 б, наведемо

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

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

33