Page 62 - 4496

U7 2
U6
U9 U8

1
U3
3

U4 U2 U10

5 4
U1
U5

Риисунок 3.6 - Граф

-
+
На рис. 3.6 для 'A = { 4,5 } ‘A = {U 4 , U 10}, ‘A = {U 2}.
Послідовність дуг, в якій кінець кожної попередньої
дуги збігається з початком наступної дуги, називають шляхом
між вершиною - початком першої дуги (початком шляху) і
вершиною - кінцем останньої дуги (кінцем шляху) . Число дуг
в послідовності приймається за довжину шляху.
На рис. 3.6 шлях між 1 і 4 вершинами складається з дуг
U , U , U , U . Між цими ж вершинами існує шлях U ,U ,
1
7
8
2
6
7
U , U , U , U , U , U , U Перший шлях має довжину 4 ,
7
2
1.
4
2
6
6
другий - 9.
Шлях назвемо простим, якщо в ньому ніяка дуга не
повторюється двічі, інакше шлях буде складеним. У прикладі
перший шлях - простий, другий - складений. Шлях назвемо
елементарним , якщо в ньому ніяка вершина не зустрічається
двічі. Будь-який складений шлях не є елементарним , простий
шлях може бути як елементарним , так і неелементарним.
Шлях , в якому початок і кінець збігаються , називається
контуром. Для контуру використовуються ті ж поняття , що і
59