5. Модифицированный алгоритм Прима-Краскала и оптимизированное проектирование сетей повышенной надежности.
Данный алгоритм можно использовать для нахождения не только кратчайшего остовного дерева, но и в более общем случае для нахождения кратчайшей связности сети в графе (это сеть соединяет тоже все вершины графа, но связность предполагается допустимой больше единицы). Вообще дерево является частным случаем связывающей сети при связности равен 1.
Шаг 1: упорядочить все ребра по уменьшении весов.
Шаг 2: рассмотреть последовательно каждое ребро графа в соответствие с рядом и определить можно ли удалить его из графа сохранить заданную связность (то есть ребро можно удалить, когда количество оставшихся независимых по ребрам путей связывающих инцидентные удаляемому ребру вершины не меньше заданной связности). Суммарный вес всех оставшихся ребер является минимальным.
Примечание: при связности больше 1 кратчайшая связывающая сеть может содержать циклы. Это исключено при связности равной 1, так как там получаем дерево.
6. Процедура ПГСГ при проектировании сетей связи с использованием графовой модели.
Для того чтобы графовую модель взвесить полностью, то есть еще и по вершинам существует специальная процедура ПГСГ (построение графа сети города). Дает возможность получить веса вершин графа.
ПГСГ состоит из 3х шагов:
1. Умножить число жителей в микрорайоне (в тыс чел) на коэффициент телефонизации. Получим число ТА в микрорайоне.
2. Чсло ТА для каждого микрорайоне разделить на число вершин графа проектной СЭГ, которые расположены непосредственно у границ этого микрорайона на плане города.
3. Для каждой вершины определить сумму чисел, полученных в п.2 по окружающим эту вершину микрорайонам. Получим вес данной вершины в количестве ТА.
После выполнения процедуры ПГСГ мы получаем полностью взвешенный граф. Веса ребер в км соответствует длинам участков улиц. Веса вершин в количестве ТА.
Как выполнить графовую модель и затем выполнить расчет процедуры ПГСГ автоматизированным способом. Микрорайоны на генплане города рисуются на экране ПК с помощью графового редактора, предназначенного для проектирования. Это фон, который формирует отдельный фоновый файл. Разметку графа на плане города легко выполнить на экране ПК с помощью этого же редактора. Например, редактора EDGR.
Для редактора Egraph есть принципиальное отличие. Он не дает возможности рисовать фон. В нем можно только рисовать граф и выполнять проектные процедуры. Фон для Egraph рисуется в одном из вспомогательных редакторов (например, Paint). Кроме того, такая открытость редактора Egraph дает возможность использовать в качестве фоновой информации системы 2Gis; AutoCAD тоже позволяет выполнять только рисунок.
Участки фона, то есть микрорайон города удобно стянуть в точку и представить в виде вершин нового графа, а затем присоединить эти вершины ребрами специального типа (обычно пунктиры) к ближайшим вершинам исходного базового графа. Граф с пунктирными ребрами считается наложенным на исходный базовый граф. Совмещенный граф – такой, который содержит ряд взвешенных элементов. Веса этих элементов должны быть введены в ПЭВМ сразу после выполнения рисунка взвешенного графа на экране, это:
1. Веса ребер базового графа в км. Они вводятся в режиме характеристики ребер подменю РЕБРА редактора EDGR в окно характеристики ч2;
2. Веса вершин наложенного графа в количестве человек (население каждого мкрн). Они вводятся в характеристики вершин, подменю ВЕРШИНЫ редактора EDGR в окно характеристик ч2 в реальных единицах.
7. Понятие передаточного числа вершины и медианы графа. Алгоритм поиска медианы графа.
При решении задач узлообразования и районирования на ЭВМ важнейшими является теоретические понятие передаточного числа и медианы графа.
Передаточное число вершины хj – это числовое значение функционала f(хj)=år(хj, ук)*Vук; хjÎx; укÎх, где r(хj; yk) – расстояние от вершины хj до вершины ук, Vук – вес вершины ук.
Пример: найти передаточные числа для вершин графовой модели. Веса вершин обозначены в скобках. Для вершины 1: j(1)=0*10+5*20+10*30=400
j(2)=0*20+5*10+6*30=230
j(3)=0*30+10*10+6*20=220
Вершина с минимальным передаточным числом в графовой модели сети называется медианой этой модели.
Если вес вершины имеет физический смысл, в нашем случае количество ТА, то при известных весах ребер (в км) полученное передаточное число тоже будут иметь физический смысл. Это сумма каналов км кабельных линий. Можно таким образом посчитать передаточные числа для каждой вершины графовой модели сети. Выбирая из полученных чисел наименьшее можно найти вершину для оптимального размещения АТС.
Алгоритм поиска медианы графовой модели телекоммуникационной сети (приближенный).
Шаг 1: выбрать произвольную вершину в графе хj и определить её передаточное число.
Шаг 2: найти вершины смежные с хj и определить для них передаточные числа.
Шаг 3: Из множества смежных вершин выбрать укÎх с наименьшим передаточным числом j(ук). Если j(ук)>j(хj), то перейти на шаг 5, если иначе то шаг 4.
Шаг 4: Для вновь найденной вершины ук повторить шаг 2 и шаг 3.
Шаг 5: вершина хj является претендующей на медиану графа (поскольку алгоритм приближенный мы говорим, что это медиана, так как в принципе может найтись еще вершина с меньшим передаточным числом).
8. В-медианы графовых моделей сетей. Общие понятия и область применения.
Обычно требуется найти оптимальные места для размещения не 1, а нескольких АТС. В этом случае используется математическое понятие b-медианы графовой модели.
В-медиана – подмножество вершин Х’ из всего множества вершин Х, причем Х’ имеет мощность равную b (|X’|=b) называется b-медианой графа, если функционал j(х’) принимает наименьшее из возможных значений (у(Х’)®min), то есть j1(Х’)=åår(хj,yk)*V(yk)®min, где хj-вершина из подмножества Х’,Хi- подмножество вершин из Х прикрепленных к вершине хj, ni- вершина из подмножества Хi, r(хj, ук)- расстояние между парой вершин хj и ук, V(ук) – вес вершины ук.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.