Page 22 - 4336

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) 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 )
0
n
називається циклічним. Циклічний маршрут називається циклом,

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

простим ланцюгом.

Наприклад, маршрут v v v v v для графа, зображеного на
0 1 2 3 0
рис. 1.9 а, є простим циклом; маршрут 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
Слід відмітити, що кожний простий цикл є циклом, а

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

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

принаймні через 3 вершини.

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

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

Приклад 1.6. На рис. 1.9 б маршрути 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
1 5 6 7 8 9
5 2 3 5 4 1 5
– простим ланцюгом; v v v v v – ланцюгом; v v v v v v – не є
8 6 7 8 7 9
7 6 8 7 9
ланцюгом.
Через C позначається граф, утворений одним простим
n
циклом з n вершин; P – простим ланцюгом з n вершин. Граф C
3
n

22