Постановка задачі синтезу мінімального остовного дерева

Зв’язністю мережі називається мінімальна кількість різних шляхів, що поєднують 2 будь-які вузли мережі. Зв’язність мережі дорівнює мінімальному рангу вузлів мережі. (Ранг вузла – кількість поєднаних з вузлом дуг)

Назвемо деревом [3] зв'язану множину неорієнтованих дуг, що не містить циклів. Якщо задана множина з m вузлів, з'єднаних неорієнтованими дугами, то для побудови дерева необхідно виділити підмножину, складену з (m-1) дуг. Іншими словами, кожний вузол дерева з'єднаний з іншим вузлом тільки одним шляхом. Отже зв’язність дерева дорівнює 1.

Розглянемо мережу, що містить n вузлів, сукупність яких утворює множину S. Остовним деревом називається зв'язна множина, складена з (n-1) дуги та n вузлів. З будь-якої підмножини множини S може бути утворене дерево, що, однак, не є остовним, якщо включає не всі вузли мережі.

Припустимо, що кожній дузі, що з'єднує вузли i та j з множини S, приписане число C_ij, що називається відстанню або вартістю дуги. Найкоротшим остовом називається такий остов мережі, у якого сума вартостей C_ij всіх його дуг мінімальна.

Існують декілька алгоритмів для розв’язання задачі побудови найкоротшого остовного дерева [2], зупинимось на алгоритмі, відомому під назвою “Алгоритм Прима”.

Алгоритм починає роботу з вибору довільного вузла мережі та найкоротшої дуги з множини дуг, що з'єднують цей вузол з іншими вузлами. З'єднаємо два вузла вибраною дугою. Оберемо найближчий до будь-якого з цих вузлів третій вузол. Додамо цей вузол та відповідну дугу до мережі. Продовжуємо даний процес до тих пір, доки всі вузли не будуть з'єднані між собою. Алгоритм, оснований на поглинанні найкоротших дуг, може бути описаний наступним чином [3].