Шаг 5: R(00101) = R(11010) = 6 | Шаг 8: R(01000) = R(10111) = 5 | ||||||||||
Вершина | 1 | 2 | 3 | 4 | 5 | Вершина | 1 | 2 | 3 | 4 | 5 |
1 | - | 999 | 6 | 7 | 6 | 1 | - | 5 | 6 | 7 | 6 |
2 | 999 | - | 6 | 7 | 6 | 2 | 5 | - | 5 | 5 | 5 |
3 | 6 | 6 | - | 6 | 7 | 3 | 6 | 5 | - | 6 | 7 |
4 | 7 | 7 | 6 | - | 6 | 4 | 7 | 5 | 6 | - | 6 |
5 | 6 | 6 | 7 | 6 | - | 5 | 6 | 5 | 7 | 6 | - |
Таблица 3.7 Таблица 3.8
Шаг 13: R(01101) = R(10010) = 3 | Шаг 15: R(01111) = R(10000) = 6 | ||||||||||
Вершина | 1 | 2 | 3 | 4 | 5 | Вершина | 1 | 2 | 3 | 4 | 5 |
1 | - | 3 | 3 | 7 | 3 | 1 | - | 3 | 3 | 6 | 3 |
2 | 3 | - | 5 | 3 | 5 | 2 | 3 | - | 5 | 3 | 5 |
3 | 3 | 5 | - | 3 | 7 | 3 | 3 | 5 | - | 3 | 7 |
4 | 7 | 3 | 3 | - | 3 | 4 | 6 | 3 | 3 | - | 3 |
5 | 3 | 5 | 7 | 3 | - | 5 | 3 | 5 | 7 | 3 | - |
Практичне заняття 4
Мета: Розглянути і отримати практичні навики побудови найкоротших кільцевих маршрутів між вузлами мережі перевезень пошти.
Ключові положення
Метод. Керівництво: “Застосування методів теорії графів для розв’язування типових задач поштового зв’язку” -, , Одеса 2000.
Кріль С. С., Ящук і та системи поштового зв’язку. – Одеса: ОНАЗ, 2008
Задача формулюється так: побудувати найкоротший кільцевий маршрут, що розпочинається і закінчується у визначеному вузлі та, як найменше, один раз проходить через кожний з решти вузлів мережі.
Сформульована задача називається задачею комівояжера і має надто складне розв’язання.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 |
