Поясняющий пример: задан граф со взвешенным ребрами, веса вершин тоже известны. Нужно найти b-медиану графа, при b=2 (физический смысл задачи: разместить оптимально 2 АТС)
1. Выбирается произвольно b-вершина в графе (b=2), таким образом формируется Х.
2. Все остальные вершины графа прикрепляются к одной из b-вершин по кратчайшему пути, то есть формируется Хi.
3. Размечается граница
4. Подсчитывают передаточные числа для каждой из b-вершин выбранных в п.1, при этом каждая часть считается отдельно.
5. Определяется функционал j1 и заполняется его численное значение j(1)=å…, j(5)=å…, j1(1,5)=åå… После этого берут следующую пару вершин и т. д.
6. Рассматривая все возможные подмножества по b-вершин данной графовой модели. Найдем минимальное значение функционала. Подмножество из b-вершин, которые обеспечивает этот минимальный функционал, является b-медианой. Пусть j1(1,3) имеет минимальное значение, значит вершины 1 и 3 являются b-медианой. В-медиана – это всегда несколько вершин. Очевидно, что минимальное количество расчета, которое обычно приходится выполнить при нахождении b-медианы равно числу сочетаний из С , где n-число вершин графовой модели, b-тип медианы.
Количество расчетов здесь может увеличиваться, когда одну вершину можно прикрепить не к одной, а к нескольким вершинам b-подмножества, так как расстояние до них одинаковое.
Для уменьшения количества расчетов при нахождении b-медианы, часто применяют один из приближенных алгоритмов поиска b-медианы.
Приближенный алгоритм поиска b-медианы, при b>1:
1. В графе G выбрать произвольно подмножества Х’ и разбить множество вершин Х на b-подмножества, таким образом чтобы произвольная вершина ук была отнесена (прикреплена) к ближайшей вершине из Х’
2. Линейно упорядочить множество вновь образовавших b-подмножеств (то есть пронумировать их 1,2,3…)
3. Рассмотреть упорядоченные на 2 шаге подмножеств последовательно. В очередном по порядку подмножестве найти вершины, которые смежны с вершиной хj принадлежащей подмножеству Х’. Определить передаточное число для каждой из этих вершин, рассматривая соответствующую часть графа как самостоятельный граф.
4. Заменить вершину хi на вершину с меньшим передаточным числом. Если такого числа нет, то перейти к шагу 5, иначе на 6.
5. Для подмножества Х’ определить значения функционала j1(Х’) и запомнить.
6. Процедуры замены и вычисления начиная с шага1 продолжить до тех пор пока не начинается увеличение j1(Х’) (то есть как только начинается увеличение после полного цикла, алгоритм закончен).Определив b-медиану графа, находим места для оптимального размещения сразу нескольких РАТС. Критерий оптимальности – минимум затрат каналов/км кабеля.
9. Понятие суграфа, подграфа и его частей. Примеры.
Суграфом G’ исходного гр.G.назыв.математ.объект,в котором число вершин Х’=Х,а число реберU’£U.Суграф получается из заданного графа путем удаления ребер при неизменном количестве вершин.
Подграфом G”исходного гр.G-это мат.объект,в котором число вершинХ”£Х,число ребер U”£U,и любая пара вершин из Х” смежна в графе G”тогда и только тогда ,когда эти вершины смежны в графеG.
Подграф можно получить из заданного исх.графа путем удаления только вершин.Ребра в подграфе специально не удаляются.
Часть графа-суграф пографа исходного графа G.
-подграф суграфа исходного графа G.
10. Алгоритм Дейкстры для определения кратчайших путей во взвешенном графе. Применение алгоритма при проектировании и моделировании телекоммуникационных сетей.
Применяется при оптимизации трассировки, а так же для решения других технических задач в области техники. Только для неотрицательных весов ребер. Тогда необходимо использовать алгоритм Флойда. Алгоритм Дейкстры:
Шаг 1: для нахождения кратчайших путей или расстояний в графовой модели сети от заданной вершины х0 до всех остальных вершин. Вес каждой вершины, кроме вершины х0 принять равной ¥. Вес вершины х0 приравнивается к 0. Она сразу будет включена в дерево кратчайших путей как корневая.
Шаг 2: из вершины х0 найти вершины графовой модели смежные с ней и их вес принять равной длине соответствующего ребра (х0, хj). Каждой из таких смежных вершин присвоить пару чисел, первое из них – номер вершины от которой пришли, второе – длина пройденного пути (в общем случае, начиная с третьего шага это длина - есть сумма вес вершины, от которой пришли плюс длина ребра, по которому шли). Вершину снабженной парой чисел называют просмотренной.
Шаг 3: из всех просмотренных вершин графа выбрать вершину с минимальным весом. Её отметить и включить в дерево кратчайших путей по ребру, по которому вершина получила минимальный вес.
Шаг 4: рассмотреть вершины, которые смежны с последней включенной в дерево вершиной, но еще не включены в будущее дерево. Определить для них пары чисел. При необходимости внести изменения в те пары чисел, где вас в результате такого изменения станет меньше. Шаги 3 и 4 повторять до тех пор, пока не будут включены в дерево все вершины графа.
Частный случай.
Возможен случай, когда все вершины, смежные с последней, включенной в дерево, тоже в это дерево включены. Но при этом можно найти какие-то другие вершины графовой модели, которые не смежны с указанной вершиной и не включены в дерево. Тогда нужно начать работу по алгоритму из той просмотренной несмежной вершины графовой модели,которая имеет минимальный вес, по сравнению со всеми просмотренными вершинами, в дерево еще не включенные. Сама эта просмотренная несмежная вершина включается в дерево по ребру, по которому она получила минимальный вес.
Примечание: если сразу несколько вершин имеют одинаковый минимальный вес, берется одна из них (любая). Пример: дан взвешенный граф. Найти кратчайшие пути (расстояние от вершины 2 как от корня до всех остальных вершин), то есть построить дерево кратчайших путей с корнем в вершине 2.
1. Вершину, включенную в будущее дерево кратчайших путей обозначают
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.