4 – 3 – 1 – 2 – 5 – 8 – 6 – 7 – 4,
протяжність якого складає 19.
Для наближення базового циклу до найкоротшого кільцевого маршруту доцільно знайти вершину, що є центром графа або його медіаною, і визначити напрямки на решту вершин графа саме з цієї вершини.
Центром графа є вершина, відстань між якою і максимально віддаленою від неї вершиною графа є мінімальною.
Медіаною графа є вершина, сума відстаней між якою та рештою вершин графа є мінімальною.
З табл. 4.1 видно, що для графа рис. 4.1 центр графа і його медіана знаходяться у вершині 6.
Будуємо напрямки N1 … N6 між вершиною 6 і рештою вершин графа (рис. 4.3).
N4 N5 
2 3 5 
4 4 3
NN6
4 3 7
 |
 |
N2 N1
Рисунок 4.3
Будуємо базовий цикл (вершину 6 вводимо в цикл за найкоротшими відстанями)
6 – 7 – 4 – 3 – 1 – 2 – 5 – 8 – 6.
Переписуємо цикл, починаючи з визначеної вершини 4
4 – 3 – 1 – 2 – 5 – 8 – 6 – 7 – 4,
який відразу співпадає з раніше одержаним скоригованим циклом.
Варіанти:
Вихідна матриця:
Вершины | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
1 | 0 | 3 | 5 | 2 | 4 | 10 | 6 | 12 |
2 | 3 | 0 | 6 | 7 | 8 | 5 | 13 | 14 |
3 | 5 | 6 | 0 | 1 | 9 | 6 | 7 | 6 |
4 | 2 | 7 | 1 | 0 | 8 | 5 | 3 | 5 |
5 | 4 | 8 | 9 | 8 | 0 | 4 | 6 | 2 |
6 | 10 | 5 | 6 | 5 | 4 | 0 | 1 | 2 |
7 | 6 | 13 | 7 | 3 | 6 | 1 | 0 | 3 |
8 | 12 | 14 | 6 | 5 | 2 | 2 | 3 | 0 |
З вихідної матриці потрібно видалити 3 вершини і 5 ребер, які вказані в таблиці.
вар | Вершины | Ребра | ||||
1 | 2 | 3 | 4 | 5 | ||
1 | 3, 1, 7 | 1-2 | 3-6 | 4-8 | 6-1 | 8-5 |
2 | 1, 2, 4 | 1-5 | 2-6 | 5-8 | 7-6 | 8-3 |
3 | 2, 3, 1 | 2-5 | 3-4 | 4-7 | 6-4 | 8-5 |
4 | 7, 4, 6 | 1-4 | 2-3 | 3-4 | 5-8 | 7-2 |
5 | 8, 5, 2 | 3-6 | 8-5 | 7-4 | 5-1 | 6-8 |
6 | 5, 6, 3 | 2-1 | 4-6 | 6-7 | 8-2 | 7-8 |
7 | 1, 8, 5 | 1-6 | 2-6 | 3-8 | 4-1 | 8-3 |
8 | 3, 7, 8 | 2-4 | 7-3 | 1-6 | 5-4 | 3-2 |
9 | 4, 8, 1 | 4-5 | 2-3 | 8-6 | 7-4 | 5-2 |
10 | 5, 7, 2 | 3-4 | 1-5 | 6-3 | 7-8 | 8-4 |
11 | 2, 6, 3 | 1-2 | 2-5 | 5-7 | 4-8 | 8-1 |
12 | 1, 5, 4 | 3-1 | 1-6 | 6-5 | 5-2 | 2-8 |
13 | 8, 4-, 5 | 4-8 | 8-3 | 3-6 | 6-7 | 7-1 |
14 | 2, 3, 6 | 1-5 | 5-4 | 4-2 | 2-3 | 3-8 |
15 | 5, 2, 7 | 5-6 | 6-1 | 1-3 | 3-5 | 4-2 |
16 | 2, 1, 8 | 1-4 | 3-2 | 3-7 | 5-6 | 6-7 |
17 | 4, 8, 1 | 2-3 | 2-8 | 6-5 | 5-4 | 3-7 |
18 | 5, 7, 2 | 1-5 | 4-3 | 3-7 | 8-6 | 6-4 |
19 | 1, 6, 3 | 2-8 | 6-4 | 5-2 | 7-1 | 1-4 |
20 | 2, 5, 4 | 8-1 | 7-2 | 6-7 | 5-8 | 1-2 |
21 | 8,4,5 | 1-3 | 4-2 | 4-6 | 7-2 | 8-6 |
22 | 1,3,6 | 1-4 | 3-4 | 5-8 | 7-8 | 2-1 |
23 | 3,2,7 | 8-5 | 6-4 | 3-8 | 8-2 | 1-3 |
24 | 5,1,8 | 8-5 | 6-4 | 3-8 | 8-2 | 1-3 |
25 | 6,8,1 | 4-3 | 2-8 | 7-5 | 8-6 | 3-6 |
26 | 4,7,2 | 1-5 | 6-3 | 1-4 | 8-3 | 5-8 |
27 | 1,6,3 | 4-5 | 1-2 | 2-7 | 6-4 | 8-5 |
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 |
