Визначення оптимального місця розташування опорного вузла в кабельній мережі абонентського доступу

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

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

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

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

Алгоритм визначення медіани графа G складається з наступних кроків.

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

Крок 2. Серед значень (Ri) відшукати мінімальне Rm. Вершина m і є медіаною графа G. Кінець роботи алгоритму.