Синтез мережі мінімальної вартості

 

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

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

З теорії графів і мереж відомо, що розв'язання поставленої задачі є мережа з топологією типу "дерево".

 

О з н а ч е н н я. Зв'язний граф (мережа, що сполучує) називається деревом, якщо в ньому є відсутні цикли.

 

Говорять, що граф містить цикли, якщо в ньому можна відшукати замкнуті контури. Відсутність циклів визначає особливість графа типу дерево, що полягає в тому, що поміж будь-якою парою його вершин існує лише один єдиний сполучуючий їх шлях, тобто параметр зв'язності h = 1. Кількість ребер у дереві завжди на одиницю менше за число його вершин.

 

О з н а ч е н н я. Дерево, в яке включено всі вершини, називається покривним.

 

Математично задача синтезу мережі мінімальної вартості формулюється таким чином.

 

Нехай задано неоріентований граф G (N, V), де множина вершин N відповідає множині пунктів мережі, сумарне число яких дорівнює n, а множина ребер V – відстаням {l_ij} поміж парами пунктів. Відома вартість С_ij організації одного кілометра лінії зв'язку поміж пунктами i та j. Необхідно знайти деяке покривне дерево G'(N, V'), для якого досягається мінімум цільової функції:

Для розв'язання поставленої задачі існує ряд ефективних алгоритмів. Наведемо один з них, відомий як алгоритм Прима, який носить ім'я автора. Алгоритм реалізовується шляхом надання позначок вершинам, що вводяться в шуканий граф G'(N, V'), і послідовного введення в нього найбільш коротких ребер, сумарна кількість яких має не перевищувати (n –1) і забезпечувати зв'язність між всіма n вершинами покривного дерева.

Покрокова форма алгоритму має такий вид.

Крок 0. Шукана мережа G'(N, V') у вихідному стані містить n вершин і не містить ребер. Обирається одна довільна вершина i й позначається як " обрана ". Інші (n – 1) вершин позначаються як " не обрані "

Крок 1. Відшукується ребро (i, j), що належить до G (N, V) з мінімальною вагою, у якої вершина i належить до підмножині " обраних " вершин, а вершина j – до підмножини " не обраних " вершин.

Крок 2. Ребро (i, j) включається в шукану мережу G'(N, V'), а вершина j виключається з підмножини " не обраних " вершин і включається в підмножину " обраних " вершин. Якщо підмножина " не обраних " вершин виявилася порожньою – кінець роботи алгоритму. В противному разі – перехід до кроку 1.

Проілюструємо роботу алгоритму Прима на прикладі. Нехай задано 7 пунктів мережі, відстані поміж яких зведено в матрицю L = || l_ij ||, а саме:

L =

 

На кроці 0 шуканий граф G'(N, V') містить 6 вершин і не містить ребер. Оберемо вершину 3 й позначимо її як " обрану" (рис. 2.2)

На кроці 1 обираємо ребро (l₃₅) як ребро з найменшою вагою, у якого вершина i = 3 належить до підмножини " обраних " вершин (воно поки містить усього лише одну вершину 3), а вершина j = 5 – до підмножині " не обраних " вершин (тепер це решта вершин). На кроці 2 ребро l₃₅ вводиться в шуканий граф G', а вершина 5 включається у підмножину " обраних " вершин (рис. 2.3).

 

Оскільки підмножина " не обраних " вершин не порожня, повторюємо крок 1. Для цього відшукуємо ребро мінімальної ваги, перебираючи сполучення кожної пари " обраної " й " недобраної " вершин. Таким виявилося ребро l₃₄ (рис. 2.4). Воно вводиться в граф G', а вершина 4 стає " обраною ".

 

 

Наступними обираються ребра: l₂₆ (рис. 2.6); l₃₁ (рис. 2.7); l₂₇ (рис. 2.8). На цьому робота алгоритму закінчується, оскільки усі вершини виявилися позначеними як " обрані " (тобто підмножина " не обраних " вершин виявилася порожньою підмножиною).

Здобуто шуканий граф G'(N, V'), що являє собою покривне дерево,оскільки він включає всі вершини, містить число ребер на одиницю менше за число вершин (n = 7, v = 6) і забезпечує зв'язність кожної пари вершин.

Визначення медіани графа

 

Розглянемо таку задачу. Нехай граф G (N, V) являє собою певну кабельну мережу, що сполучує n абонентських пунктів. Вага кожного ребра (i, j), що належить до V, відповідає довжині l_ij або вартості кабелю, що сполучує пункти i та j. Необхідно визначити деяку вершину m, що належить до N, в якій доцільно розмістити вузол комутації (наприклад, районну АТС) з погляду мінімізації сумарної довжини кабелю, що сполучує абонентські пункти з УК.

Розв'язанням поставленої задачі є визначення медіани графа G (N, V).

О з н а ч е н н я. Вершина m, що належить до N, є медіана графа G(N, V), якщо вона задовольняє умові:

 

 

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

Алгоритм визначення медіани графа G включає такі кроки.

Крок 1. У вихідній матриці ваг L = [ l_ij ], відповідній довжинам ребер, знайти суму елементів для кожного рядка:

 

 

Крок 2. Серед множини значень {R_i} відшукати мінімальне R_m. Вершина m і є медіана графа G.

 

 

Визначення центра графа

 

Припустимо, що задано місцеположення пунктів абонентської мережі, в якій реалізовується стаціонарний радіо доступ до опорного вузла базової мережі. Необхідно серед пунктів абонентської мережі визначити місцеположення базової станції (БС), котра по радіоканалах зв'язується з абонентськими пунктами (АП). Бажано, щоби відстань від БС до будь-якого АП була мінімальною, що забезпечить стійкий радіозв'язок за меншої потужності передавача БС. Вочевидь, що такому критерію задовольнити неможливо, тому доводиться мінімізувати відстань до самого віддаленого пункту. При цьому доцільно, щоб БС за можливістю зайняла центральне положення щодо всіх ОП.

 

Задача знаходження такого пункту може бути зведена до задачі знаходження центра графа.

 

О з н а ч е н н я. Нехай G (N, V) є граф, де N – множина вершин, а V - множина відстаней поміж всіма вершинами. Вершина s називається центром графа G (N, V), якщо вона задовольняє умові:

для будь-якої i;

 

Алгоритм знаходження центра графа (вершини s) виходить з самого визначення:

Крок 1. У кожному рядку вихідної матриці ваги L = [ l_ij ] – знайденний елемент з максимальним значенням.

Крок 2. Серед множини максимальних значень елементів рядків відшукуємо найменше l_sj {l_ij}. Вершина s є центр графа.

Таким чином, мінімізувавши відстань від точки s до самої віддаленої вершини, ми забезпечили до решти вершин гарантовано меншу відстань.