Page 83 - 2589

Розв’язок. Даний граф наведено на рис. 2.1

Рисунок 4.4 – Побудова графа за заданим відображенням

5.6 Граф типу дерево

Граф G називається деревом, якщо він є зв'язним і не має
циклів, а граф G , усі компоненти зв'язності якого є деревами –
лісом.

Прикладом графа типу дерево, зображений на рис. 4.8.
Розглянемо деякі властивості дерев.

Рисунок 4.5 – Приклад графа типу дерево

Наступні твердження є еквівалентними:

1) граф G – дерево;
2) граф G є зв'язним і не має простих циклів;

3) граф G є зв'язним, і (Gn )  m (G )  ; 1 ;

4) для будь-яких двох різних вершин графа G існує єдиний (і
притому простий) ланцюг;
5) граф G не містить циклів, але, додаючи до нього будь-яке
нове ребро, дістаємо рівно один і притому простий цикл.

5.7 Задача про найкоротший шлях
5.7.1 Постановка задачі

У практичних застосуваннях має велике значення завдання
про знаходження найкоротшого шляху між двома вершинами
зв'язного неорієнтованого графа. До такого завдання зводяться
багато завдань вибору найбільш економічного (з точки зору

відстані або часу або вартості) маршруту на наявній карті доріг,

83