Page 111 - 4204

ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ

Для прикладу, розглянемо граф що відповідає 5-ти населеним пунк-

там А, Б, В, Г та М, де кожні два пункти сполучені дорогою (рис. 8.2).

Такий граф називається повним. Числа на лініях вказують відстані між

населеними пунктами по цих дорогах.

6
Б
В

7
11
13 9
10
A
6
5
Г

7
4

M

7 4
10 6
A Б В Г

7 11 5 7 6 13 11 6 9 5 13 9

Б В Г A В Г A Б Г A Б В

6 13 6 9 13 9 11 5 11 9 5 9 7 5 7 13 5 13 7 11 7 6 11 6

B Г Б Г Б B B Г А Г А B Б Г A Г А Б Б B А B А Б
9 9 13 13 6 6 9 9 5 5 11 11 13 13 5 5 7 7 6 6 11 11 7 7

Г B Г Б B Б Г B Г А B А Г Б Г A Б А B Б B А Б А
4 6 4 10 6 10 4 6 4 7 6 7 4 10 4 7 10 7 6 10 6 7 10 7

M M M M M M M M M M M M M M M M M M M M M M M M
30 42 44 50 37 37 41 37 36 37 45 50 41 45 28 37 37 42 28 36 41 44 41 30

Рисунок 8.2. Всеможливі варіанти замкнутих маршрутів комівояжера
та відповідних пройдених відстаней

Нехай вершина M – вихідний пункт (оскільки усі маршрути замкну-

ті, то вибір початкового пункту не принциповий). Тоді будемо мати 4 ва-

110