Размещение центров на многовзвешенных предфрактальных графах

Размещено на http://www.allbest.ru/

РАЗМЕЩЕНИЕ ЦЕНТРОВ НА МНОГОВЗВЕШЕННЫХ ПРЕДФРАКТАЛЬНЫХ ГРАФАХ

Постановка задачи

Рассматривается предфрактальный граф , порожденный множеством затравок . Каждому ребру приписано действительных чисел

,

, где ранг ребра, , и коэффициент подобия.

Пусть подмножество, состоящее из вершин множества предфрактального графа . Через обозначаем наикратчайшее из расстояний между вершинами множества и вершиной , т.е. .

Число разделения для множества вершин определяется следующим образом . Множество , для которого , называется -центром предфрактального графа .

На рис. 1 изображен предфрактальный граф с сохранением смежности старых ребер, веса ребер взвешены единицами. Кратчайшая цепь между множеством и вершиной выделена пунктирной линией. Длина кратчайшей цепи или наикратчайшее из расстояний . Число разделения -центра .

Всевозможные -центры предфрактального графа образуют множество допустимых решений (МДР) [1, 2].

На множестве определим векторно-целевую функцию (ВЦФ):

,

, ,

где - число разделения множества ;

, ,

- радиус -вершины -центра;

,

- количество типов центров (количество центров разного ранга);

,

- количество вершин, составляющих -центр.

Все критерии (2)-(5) ВЦФ (1) имеют конкретную содержательную интерпретацию. Веса, приписанные ребрам предфрактального графа , могут отражать как конкретные ограничения (время, расстояние), налагаемые на систему служб (аварийные, пожарные депо, полицейские участки, больницы), так и общие затраты, выражаемые в условных единицах.

Полученное значение числа критерия (5) будет наименьшим числом аварийных служб, а р-центр их оптимальным размещением, удовлетворяющим предъявляемым требованиям. Поскольку веса одного ребра несравнимы, паретовское множество включает в себя -центры не одного набора весов, а каждого из . Критерий минимизирует число разделения, а критерий минимизирует сумму радиусов -центра по _му набору весов, .

Оценка радиального критерия предфрактальных графов

Рассмотрим вначале некоторые определения и обозначения. Длина кратчайшего пути, соединяющего пару вершин , называется расстоянием между вершинами w и v и обозначается через . Для фиксированной вершины величина называется эксцентриситетом вершины . Эксцентриситет, максимальный среди всех эксцентриситетов вершин графа , называется диаметром графа H и обозначается через , т.е. [3].

Если пара вершин соединяется кратчайшим путем длины , то этот путь называется диаметральным. Вершина w называется периферийной, если . Радиус графа H обозначается через и вычисляется по формуле .

Рассмотрим предфрактальный граф , порожденный затравкой-звездой , всем ребрам которого приписан вес равный единице, а коэффициент подобия равен 1. Вычислим верхние и нижние оценки радиуса предфрактального графа , траектории .

Радиус графа равен единице, так как есть затравка-звезда: . Центром графа является вершина, смежная со всеми остальными вершинами. Расстояние от центра до любой другой вершины равно единице. В случае, если смежность старых ребер графа сохраняется, радиус . Если старые ребра не пересекаются и инцидентны висячим вершинам подграф-затравок, радиус . Верхняя и нижняя оценки радиуса предфрактального графа с произвольной смежностью старых ребер равна: .

На рис. 2 представлены предфрактальные графы и , порожденный 4_вершинной затравкой-звездой. Для графа рассмотрены два варианта порождения: сохранение смежности и непересечение старых ребер. Центры обведены малыми пунктирными окружностями.

По аналогии с предыдущими вычислениями, верхняя и нижняя оценки радиуса графа равны: (см. рис. 3.а и 3.б).

Продолжая процесс вычисления верхних и нижних оценок радиуса, получим, что и , для всех .

Верхние и нижние оценки радиуса графа , равны:

;

;

;

;

.

Тогда оценка радиуса предфрактального графа выражается неравенством: для всех . Верна следующая теорема.

Теорема 1. Для всякого предфрактального графа , порождённого затравкой-звездой, радиус для всех .

Вычислим далее верхнюю и нижнюю оценки диаметра предфрактального графа , :

; ;

; ;

; ;

; ;

; .

Тогда оценка диаметра предфрактального графа выражается неравенством для всех . Верна следующая теорема.

Теорема 2. Для всякого предфрактального графа , порождённого затравкой-звездой, диаметр для всех .

Примечание 1. Оценки радиуса и диаметра , верны для всякого предфрактального графа , порождённого n_вершинной затравкой-звездой.

На рис. 2 и 3 цепи (выделены пунктирными линиями) между вершинами и отражают значение радиуса, а между и - значение диаметра. радиальный предфрактальный граф математический

Алгоритм размещения центра предфрактального графа при сохранении смежности старых ребер

Рассмотрим предфрактальный граф , порожденный множеством затравок , смежность старых ребер которого сохраняется. Опишем применение алгоритма для одного фиксированного набора весов из и далее обобщим для каждого _го набора, [4, 5]. Алгоритм начинает свою работу с подграф-затравок _го ранга , . На последнем шаге порождения предфрактального графа каждая вершина графа была замещена затравкой . Поскольку при порождении предфрактального графа действует правило сохранения смежности старых ребер, к каждой вершине склеиваются затравки одной из своих вершин.

Рассмотрим подграф-затравку , так как затравка является сильно связанной, то для всякой ее вершины можно найти путь к любой другой. Найдем кратчайшие цепи от «общей» вершины до оставшихся вершин подграф-затравки . Среди кратчайших путей выбираем максимальный и определяем число

,

которое называется числом разделения вершины подграф-затравки . Далее поочередно осуществляется поиск чисел разделения

, ,

где для общих вершин всех подграф-затравок _го ранга. Поиск кратчайших путей осуществляется с помощью известного алгоритма Дейкстры, оформленного в виде процедуры.

Рассмотрим далее подграф-затравки _го ранга , . Каждая из них в процессе порождения предфрактального графа была склеена к вершинам предыдущего в траектории графа , так как действует правило сохранения смежности старых ребер. Тогда каждая подграф-затравка -го ранга также имеет одну общую вершину с соответствующими затравками -го ранга ,

.

Найдем числа разделения для каждой общей вершины подграф-затравок _го ранга , следующим образом: , где . То есть находим кратчайшие пути от общей вершины до оставшихся вершин подграф-затравки . Добавляем к длине кратчайшего пути соответствующее число разделения , найденное для подграф-затравок предыдущего ранга, и среди получившихся сумм выбираем максимальную. Сумма , так как . Указанным способом находим числа разделения для общих вершин , подграф-затравок до 2-го ранга включительно, то есть для всех . На последнем шаге найдены числа разделения , для общих вершин подграф-затравок 2-го ранга и одной подграф-затравки первого ранга . Подграф-затравка , по сути, соответствует графу траектории . Тогда для каждой вершины подграф-затравки найдено число

, .

Далее рассматриваем подграф-затравку как отдельный граф и находим для каждой ее вершины число разделения следующим образом:

.

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

Теорема 3. Алгоритм осуществляет поиск центра предфрактального графа , смежность старых ребер которого сохраняется.

Следствие 1. Алгоритма выделяет центр , предфрактального графа , смежность старых ребер которого сохраняется.

Алгоритм осуществляет поиск центра для фиксированного набора весов. Применение алгоритма по каждому набору весов позволяет находить центры .

Теорема 4. Вычислительная сложность алгоритма на предфрактальном графе , порожденном затравкой , равна , где и .

Следствие 2. Вычислительная сложность алгоритма поиска центров , на предфрактальном графе , порожденном затравкой , равна , где и .

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

Теорема 5. Алгоритм выделяет центр на предфрактальном графе , оптимальный по критериям и , и оцениваемый по критерия

, .

На рис. 4 представлен пример поиска центра предфрактального графа для случая . Предфрактальный граф взвешен в соответствии с правилом взвешивания ребер, где начальный отрезок , а весовой коэффициент . Алгоритм поиска центра начинает свою работу с подграф-затравок 3_го ранга. Внутри подграф-затравок мелким шрифтом указаны числа разделения общих вершин. Центром графа является вершина , для которой число разделения минимальное: . Радиус предфрактального графа равен числу разделения вершины : . Значения критериев . Оценки критериев следующие:

;

.

Оценка критериев верна: .

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 16 - 07 - 00231а. The reported study was partially supported by RFBR, research project № 16 - 07 - 00231а.

Список литературы

1. Перепелица В.А. Многокритериальные модели и методы для задач оптимизации на графах. - LAP LANDERT Academic Publishing. - 333 с.

2. Кочкаров А.М. Распознавание фрактальных графов. Алгоритмический подход. - Нижний Архыз: РАН САО, 1998. - 170 с.

3. Кочкаров А.А., Малинецкий Г.Г., Кочкаров Р.А. Некоторые аспекты динамической теории графов // Журнал вычислительной математики и математической физики, 2015, том 55, № 9. - С. 1623-1629.

4. Узденов А.А., Кочкаров Р.А. Алгоритм поиска центра предфрактального графа, смежность старых ребер которого сохраняется // Вестник Северо-Кавказского государственного технического университета. - Ставрополь.: СевКавГТУ, 2011. - № 1 (26). - С. 50-53.3.

5. Кочкаров Р.А. Задачи многокритериальной оптимизации на многовзвешенных предфрактальных графах. - М.: Академинновация, 2014. - 189 с.

Аннотация

Кочкаров Расул Ахматович Токова Алла Аскеровна Кочкарова Асият Нерчуковна

Северо-Кавказская государственная гуманитарно-технологическая академия, Черкесск, Россия

В работе предложена многокритериальная постановка задачи размещения центров на многовзвешенном предфрактальном графе. Приведена оценка радиального критерия предфрактального графа, порожденного затравкой-звездой. Предложен полиномиальный алгоритм размещения центра предфрактального графа при сохранении смежности старых ребер. Проведена оценка вычислительной сложности алгоритма и рассмотрен пример работы алгоритма

Ключевые слова: МНОГОКРИТЕРИАЛЬНАЯ ЗАДАЧА, МНОГОВЗВЕШЕННЫЙ ГРАФ, ПРЕДФРАКТАЛЬНЫЙ ГРАФ, РАЗМЕЩЕНИЕ ЦЕНТРА, ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ

CENTERS PLACEMENT ON MANY-WEIGHTED PREFRACTAL GRAPHS

Kochkarov Rasul Akhmatovich Tokova Alla Askerovna

Kochkarova Asiyat Nerchukovna

North-Caucasian State Humanitarian Technological Academy, Cherkessk, Russia

Multicriterial formulation for centers placement problem on many-weighted prefractal graph is proposed. Estimation of the radial criterion of prefractal graph generated by seed-star is shown. Polynomial algorithm centers placement on prefractal graph with preserving contiguity old edges is suggested. Estimation of computational complexity of the algorithm and the example of the work algorithm are considered

Keywords: MULTICRITERIAL PROBLEM, MANY-WEIGHTED GRAPH, PREFRACTAL GRAPH, CENTER PLACEMENT, COMPUTATIONAL COMPLEXITY

Размещено на Allbest.ru