Випадок 4: збереження раніше сформованих фрагментів

У цьому випадку обидві кінцеві вершини перевірного ребра належать деякому раніше сформованому фрагменту. Перевірне ребро не включається до складу жодного з фрагментів.

Процес перевірки ребер закінчується, коли всі вершини графа увійдуть в один фрагмент, або коли загальна кількість ребер, що увійшла в зазначений фрагмент, дорівнює числу вершин графа, зменшеному на одиницю.

Алгоритм побудови графа з мінімальною сумарною вагою ребер наведений на рис. 2.2.

Алгоритм містить 10 блоків.

У блоці 1 провадиться введення в довільному порядку переліку ребер початкового графа з зазначенням їх ваг.

У блоці 2 здійснюється вибір чергового перевірного ребра мінімальної ваги згідно з будь-яким алгоритмом пошуку мінімального числа.

У блоці 3 з переліку ребер початкового графа виключається перевірне ребро для запобігання його повторного вибору.

У блоці 4 перевіряється умова формування нового фрагмента (випадок 1). В разі виконання умови – перехід до блоку 5, в разі невиконання – до блоку 6.

У блоці 5 провадиться формування нового фрагмента.

У блоці 6 перевіряється умова розширення існуючого фрагмента (випадок 2). В разі виконання умови – перехід до блоку 7, в разі невиконання – до блоку 8.

У блоці 7 провадиться формування розширеного фрагмента.

У блоці 8 перевіряється умова об’єднання двох існуючих фрагментів (випадок 3). В разі виконання умови – перехід до блоку 9, в разі невиконання – до блоку 10.

У блоці 9 провадиться формування об’єднаного фрагмента.

У блоці 10 перевіряється умова закінчення формування графа. В разі невиконання умови – повернення до блоку 2, в разі виконання – закінчення роботи алгоритму.

Зазначимо, що оскільки перевірка будь-якого ребра завжди призводить до одного з чотирьох зазначених випадків, достатньо перевірити умови виконання лише трьох з них, тому в наведеному алгоритмі умова виконання випадку 4 не перевіряється.

 

Початок

 

1. Введення переліку

ребер початкового

графа

 

2. Вибір чергового перевірного

ребра мінімальної ваги

 

3. Виключення перевірного

ребра з переліку ребер

початкового графа

4. Жодна

з кінцевих вершин Так 5. Формування нового фрагмента з

перевірного ребра не належить перевірного ребра і двох його

жодному фрагменту кінцевих вершин

 

Ні

6. Перша

кінцева вершина 7. Включення перевірного ребра

перевірного ребра належить Так і його другої кінцевої вершини

деякому фрагменту, а друга - не до фрагмента, якому належить

належить жодному перша кінцева вершина зазначе-

фрагменту ного ребра

 

Ні

8. Перша

кінцева вершина пере- 9. Формування об’єднаного

вірного ребра належить одному Так фрагмента з перевірного ребра

фрагменту, а друга - іншому і двох фрагментів, яким належать

фрагменту його кінцеві вершини

 

Ні

 

10. Всі

Ні вершини графа

увійшли в один фрагмент

 

 

Так

Кінець

 

 

Рисунок 2.2. Алгоритм побудови графа з мінімальною сумарною вагою ребер

Наведемо приклад побудови найкоротшої мережі перевезень пошти. Граф початкової мережі зображений на рис. 2.3. Біля ребер графа зазначені їх ваги.

2 5

3

4 4 3

 

1 1 3 3 6 2 8

 

4 2 4 1 4

 

4 3 7

 

Рисунок 2.3. Граф початкової мережі

 

У табл. 2.1 наведений перелік ваг ребер початкового графа.

Таблиця 2.1. Перелік ваг ребер початкового графа

Ребро	(1,2)	(1,3)	(1,4)	(2,5)	(2,6)	(3,4)	(3,6)	(4,6)	(4,7)	(5,8)	(6,7)	(6,8)	(7,8)
Вага

 

У табл. 2.2 наведено послідовність кроків формування графа з мінімальною сумарною вагою ребер

Таблиця 2.2. Послідовність кроків формування графа з мінімальною сумарною вагою ребер

Крок	Перевірне ребро	Вага перевірного ребра	Вершини
Фрагмент 1	Фрагмент 2	Фрагмент 3
	(1,3)		1,3
	(6,7)		1,3	6,7
	(3,4)		1,3,4	6,7
	(6,8)		1,3,4	6,7,8
	(2,5)		1,3,4	6,7,8	2,5
	(3,6)		1,3,4,6,7,8		2,5
	(4,7)		1,3,4,6,7,8		2,5
	(5,8)		1,3,4,6,7,8,2,5

 

Усього для формування графа з мінімальною сумарною вагою ребер знадобилось 8 кроків, при чому крок 7 (перевірка ребра (4,7)) виявився зайвим.

На рис. 2.4 наведений граф, на якому жирними лініями виділене дерево з мінімальною сумарною вагою ребер.

 

 

2 5

3

4 4 3

 

1 1 3 3 6 2 8

 

4 2 4 1 4

 

4 3 7

 

Рисунок 2.4. Дерево з мінімальною сумарною вагою ребер.

 

В наведеному прикладі сумарна вага ребер початкового графа складає 38, а дерева з мінімальною сумарною вагою ребер – 15.

Зазначимо, що за іншим порядком перевірки ребер однакової ваги можна отримати інше дерево з мінімальною сумарною вагою ребер, але значення цієї сумарної ваги не зміниться.