Определение оптимального местоположения. Перечень рекомендуемой литературы

Лекция 8

Перечень рекомендуемой литературы.

опорного узла в кабельной сети абонентского доступа

Рассмотрим следующую задачу. Пусть граф 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.

Дата добавления: 2014-01-07