Випадок 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 не перевіряється.

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

Початок

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

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

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

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

графа

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

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

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

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

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

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

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

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

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

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

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

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

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

Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru перевірного ребра не належить перевірного ребра і двох його

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

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

Ні

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

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

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

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

Випадок 4: збереження раніше сформованих фрагментів - student2.ru деякому фрагменту, а друга - не до фрагмента, якому належить

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

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

Ні

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

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

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

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

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

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

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

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

10.Всі

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

Випадок 4: збереження раніше сформованих фрагментів - student2.ru увійшли в один фрагмент

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

Так

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

Кінець

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

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

2 5

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

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

4 4 3

Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru 1 1 3 3 6 2 8

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

4 2 4 1 4

Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru 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

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

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

4 4 3

Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru Випадок 4: збереження раніше сформованих фрагментів - student2.ru 1 1 3 3 6 2 8

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

4 2 4 1 4

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

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

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

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

Наши рекомендации