Page 301 - 6197

Рисунок Д3.6 –

Рисунок Д3.5 – Зв’язаний Незв’язаний граф
граф
Слід відмітити, якщо шлях не є простим (має вершини, які
повторюються більше одного разу), то вилучивши частини
шляху між двома появами вершини V , можна отримати
i
простий шлях.
Наприклад, розглянемо шлях (рис. Д3.5)
V V V VV V V VV V V V V , вилучивши частини шляху V VV V і
0 3 4 1 0 3 4 1 2 5 4 6 7 4 1 0 3
VV V V , отримаємо простий шлях V V V V V .
1 2 5 4 0 3 4 6 7
Число ребер маршруту визначають його довжину. У тому
випадку, коли кожному ребру графа поставлено у
відповідність деяке число c - вага ребра, то граф є зваженим.
ij
У зваженому графі довжина маршруту (шляху) визначається
сумою ваг ребер, які утворюють маршрут.
Циклом називають шлях ненульової довжини, який з’єднує
вершину саму з собою і не вміщує ребер, що повторюються.
Простим циклом називають шлях ненульової довжини,
який з’єднує вершину саму з собою і не вміщує вершин, що
повторюються, крім початкової вершини.
Приклад Д3.3. Цикл графа V V V VV , що зображений на
0 3 4 1 0
рис. Д3.5, є простим циклом, а цикл V VV V V V V V V таким
0 1 4 5 7 6 4 3 0
не являється.

301