Page 33 - 4386

Слід відмітити, що кожний простий цикл є, в свою чергу,

циклом, а довжина будь-якого нетривіального замкненого

маршруту (v v …v v ), де v =v , з попарно різними ребрами є не
0 1
n-1 n
n
0
менша 3, оскільки треба вийти з вершини та повернутися в неї,
але по різних ребрах. Отже, цикл і простий цикл повинні

проходити принаймні через 3 вершини.

Довжина довільного простого циклу в графі завжди не

більша числа вершин n, а простого ланцюга – менша n.

Приклад 3.2. На рис. 3.1 б маршрути v v v v , v v v v та
1 5 4 1
2 3 5 2
v v v v v є простими циклами; v v v v v v v є циклом; v v v v v v
6 8 9 7 6
5 2 3 5 4 1 5
1 5 6 7 8 9
– простим ланцюгом; v v v v v – ланцюгом; v v v v v v – не є
7 6 8 7 9
8 6 7 8 7 9
ланцюгом.
Через C позначається граф, утворений одним простим
n
циклом з n вершин; P – простим ланцюгом з n вершин. Граф C
3
n
часто називається трикутником. Це цикл і простий цикл з

найменшою кількістю вершин.

Граф, що не має циклів, називається ациклічним.

3.2 Маршрути в орієнтованому графі

Послідовність дуг, у якій кінець кожної попередньої дуги e
і-1
збігається з початком наступної e , називається шляхом або
і
орієнтованим маршрутом. У шляху одна і та сама дуга може

зустрічатися кілька разів.

Початком шляху є вершина v дуги e , а кінцем шляху є
1
0
вершина v дуги e .
n
n
Довжиною орієнтованого маршруту називається кількість

дуг, що входять у цей маршрут.

32