Математическая модель организации распределенных вычислений в корпоративной сети на предфрактальных графах в векторной постановке

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

Математическая модель организации распределенных вычислений в корпоративной сети на предфрактальных графах в векторной постановке

В настоящее время деятельность крупных организаций, связанных с анализом информации и принятием определенного решения, не мыслима без использования ЭВМ. При работе с большим объемом информации, некоторые организации используют распределенные вычислительные системы [1], входящие в функции корпоративной сети, состоящие из большого количества ЭВМ, соединенных между собой линиями связи.

В качестве примера таких организаций с корпоративной сетью и распределенной вычислительной системой можно привести центральный пункт управления полетами, транспортом, финансовые биржи, военные ведомства и т. д. В структуру корпоративной сети большинства из них входит множество секций, которые состоят из совокупности ЭВМ связанных между собой линиями связи. При решении задачи, функции секций заключается в том, что они обрабатывают информацию на некотором этапе. Затем, происходит объединение секции в отделы, которые производят анализ информации переданной по линиям связи от секций. В свою очередь, отделы объединяются в ведомства и работают с информацией, переданной с отделов. Аналогично, соединяются подразделения всей организации, составляющие корпоративную сеть и т. д. Процесс объединения происходит до тех пор, пока на некотором этапе определенная структура, контролирующая всю корпоративную сеть, проанализировав информацию, примет определенное решение.

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

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

Оговоримся заранее, что в работах [2, 3] можно найти недостающие термины и определения теории графов и предфрактальных графов.

Приведем основные определения.

Затравкой назовем связный n-вершинный граф , где W -множество вершин, а Q - множество ребер.

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

Предфрактальный граф назовем (n,L)-графом, если затравкой является полный n-вершинный граф.

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

Приведем постановку рассматриваемой задачи в терминах теории графов [3] и многокритериальной дискретной оптимизации [4].

Рассматриваемая задача сводится к широкому классу задач о покрытиях предфрактальных графов [5-19].

Распределение определенной задачи по элементам сети есть покрытие предфрактального графа простыми непересекающимися цепями [5-7, 11].

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

Цепью предфрактального графа назовем простую цепь C, в которой количество вершин есть длина цепи, которую обозначим . Простую цепь, содержащую ребра одинакового ранга l, назовем l-ранговой цепью и обозначим С^(l).

Покрытием графа назовем подграф , состоящий из множества простых цепей, где каждая вершина инцидентна ребрам только одной цепи из y. Совокупность всех покрытий предфрактального графа образуют множество допустимых решений (МДР) .

На графе качество покрытия y определяется векторно-целевой функцией (ВЦФ):

корпоративный сеть предфрактальный граф

(1)

_

, (3)

где - мощность покрытия, определяющее количество цепей в покрытии y

(4)

где - количество типов цепей в покрытии y.

В ВЦФ (1) критерии (2)-(4) имеют содержательную интерпретацию для исследуемой задачи.

Распределение задачи между ЭВМ определяет критерий (2), позволяющий минимизировать общую степень отказа.

Критерий (3) позволяет сократить время обработки информации в корпоративной сети с распределенной вычислительной системой.

Критерий (4) позволяет равномерно распределить задачи между элементами сети, чтобы не перегружать отдельные ЭВМ.

Алгоритм

Пусть дан взвешенный предфрактальный граф порожденный затравкой , где , .

Алгоритм строит покрытие цепями длины ребро оптимальное по критерию .

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

Смысл теоремы заключается в том, что если найдется совершенное паросочетание (СП) [2] на затравке , тогда найдется СП на предфрактальном графе .

Пусть алгоритм выделяет совершенное паросочетание минимального веса (СПМВ) [2] и выполняется условие теоремы 1.

АЛГОРИТМ

Вход: взвешенный предфрактальный граф .

Выход: СПМВ .

Шаг 1. Последовательно для каждой затравки , найти СП , используя алгоритм Эдмондса [3].

Шаг 2. На выходе шага 1 получаем СПМВ , для каждой затравки . Объединяя СП , получим СПМС предфрактального графа .

Процедура Эдмондса.

Вход: взвешенный граф

Выход: СПМВ <

Теорема 2. Алгоритм на предфрактальном -графе выделяет СПМВ , если .

Доказательство. На подграф-затравках с помощью алгоритма Эдмондса осуществляется поиск СПМВ.

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

Отбросим все ребра ранга , и будем рассматривать только подграф-затравки L-го ранга , .

Выделим на подграф-затравке L-го ранга СПМВ , которое покрыло n вершин. Аналогично, выделим на второй затравке L-го ранга СПМВ , которое покрыло еще n вершин, не повлияв на , так как затравки и не связанны между собой.

На последней затравке , после выделения СП будет покрыто вершин. В результате получим, что все множество вершин оказалось покрытым.

На затравках выделились СП , , т. е. вершины предфрактального графа покрывались паросочетанием. В результате полученное покрытие является СП предфрактального графа . А так как предфрактальный граф является взвешенным с помощью коэффициента , вес ребра L-го ранга меньше веса любого ребра предыдущих рангов. В результате поиск СПМВ производился на ребрах самых минимальных весов, т. е. СП выделенное на предфрактальном графе будет иметь минимальный вес. <

Теорема 3. Вычислительная сложность алгоритма , покрытия цепями длины один (ребро) минимального веса на предфрактальном -графе , порожденного затравкой , где , равна

Доказательство. Алгоритм находит паросочетания для каждой из подграф-затравки. Вычислительная сложность Шага 1 равна операций. Тогда на всем предфрактальном графе вычислительная сложность алгоритма равна

<

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

Теорема 4. Алгоритм выделяет покрытие на предфрактальном -графе , порожденном n-вершинной затравкой , оптимальное по критериям и и оцениваемое по критерию .

Доказательство. Теорема 2 служит доказательством оптимальности по критерию , поскольку в результате работы алгоритма получаем СПМВ.

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

.

Алгоритм

Построим алгоритм покрытия взвешенного предфрактального -графа порожденного затравкой , цепями длины два (два ребра), где , , а n кратно трем. Алгоритм выделяет покрытие простыми цепями длины два ребра.

Каждая подграф-затравка , рассматривается как отдельно взятый граф, в этом заключается основная идея алгоритма. На каждой из подграф-затравке используя процедуры Выделения покрытия цепями длины два производится поиск покрытий простыми цепями длины два. В работе процедуры используется алгоритм Эдмондса [2]. На подграф-затравках произведя поиск покрытий простыми цепями длины два, мы построим покрытие на всем предфрактальном графе . В результате алгоритм заканчивает свою работу.

Кратко опишем процедуры Выделения покрытия цепями длины два, в которой на взвешенном графе с помощью алгоритма Эдмондса производится поиск СПМВ . Среди элементов СПМВ выделяется элемент , имеющий максимальный вес. Далее, у выбранного элемента рассматриваются концевые вершины и выбираются инцидентные им ребра графа G, из которых выделяются ребра имеющие минимальный вес. В результате два элемента покрытия , соединяются выделенными ребрами и образуются в отдельности друг от друга цепи . Каждую цепь рассматривается в отдельности и выбирается с минимальным весом. У выбранной минимальной цепи , выбирается из двух ребер принадлежащих покрытию ребро с минимальным весом. Ребро с максимальным весом, принадлежащее покрытию , исключаем из цепи . У исключенного ребра, принадлежащего , запоминается и окрашивается конечная вершина. В результате проделанных шагов выделяется цепь длины два. Многократное выполнение описанной операции покроет весь граф G цепями длины два.

АЛГОРИТМ

Вход: взвешенный предфрактальный граф

Выход: покрытие простыми цепями длины два.

Шаг 1. Последовательно для каждой затравки , используя процедуру ПЦДД, найти покрытие простыми цепями длины два.

Шаг 2. По завершению шага 1 получаем для каждой затравки покрытий . Покрытие предфрактального графа получается объединением покрытий .

Процедура Выделения покрытия цепями длины два (ПЦДД).

Вход: взвешенный граф .

Выход: покрытие M простыми цепями длины два.<

Теорема 5. Алгоритм строит покрытие цепями длины два (два ребра) на предфрактальном графе , порожденного n-вершинной затравкой , где n кратно трем, при условии существования покрытия.

Доказательство. С помощью процедуры ВПЦДД на подграф-затравках производится поиск цепей длины два.

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

Выделим на подграф-затравке L-го ранга покрытие . В результате покрытие выделило n вершин. Затем выделим покрытие на второй затравке L-ого ранга . Выделилось еще n вершин покрытием . Так как подграф-затравки и являются отдельными не связанными подграфами, то покрытие никак не затронуло .

После выделения покрытия на последней подграф-затравке будет покрыто вершин. В результате все множество вершин : | будет покрыто.

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

Теорема 6. Алгоритм покрытия цепями длины два (два ребра) на предфрактальном (n,,L)-графе порожденного затравкой где , , имеет вычислительную сложность равную .

Доказательство. По сути, алгоритм представляет собой поиск покрытия длины два ребра для каждой подграф-затравки, т. е. многократное выполнение шага 1 Для каждой затравки, сначала производится поиск СПМВ, что требует выполнения операций на каждой подграф-затравке, а их . Затем все ребра паросочетания просматриваются и находится наибольшее. В результате выполняется операций. Далее у всех ребер паросочетания просматриваются все смежные ребра. Когда затравкой является полный граф, тогда для каждой вершины алгоритм просмотрит (n-1) ребер. Количество всех выполненных операций составит . Далее для всех элементов покрытия цепями два ребра будет просмотрено по две цепи длины три ребра, что составит операций.

В результате получим

.

На затравке количество операций будет равняться =2 и вычислительная сложность алгоритма на предфрактальном графе будет равна . <

Теорема 7. Алгоритм выделяет покрытие на предфрактальном -графе порожденном затравкой , оптимальное по критерию и оцениваемое по критерию, и по критерию,, если .

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

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

.

Алгоритм

Рассмотрим взвешенный предфрактальный граф порожденный затравкой , , где n кратно четырем. Покрытие простыми цепями длины три (три ребра) выделяется алгоритмом .

Аналогично, работе алгоритма каждую подграф-затравку , будем рассматривать как отдельно взятый граф. Поиск покрытий простыми цепями длины три ребра последовательно производится на каждой из подграф-затравок. На отдельно взятой подграф-затравке поиск покрытия осуществляется с помощью процедуры Выделения покрытия цепями длины три (ВПЦДТ). В основе ВПЦДТ лежит алгоритм Эдмондса. На всех подграф-затравках проведя поиск покрытий простыми цепями длины три, получим покрытие предфрактального графа простыми цепями длины три ребра. После этой процедуры алгоритм заканчивает свою работу.

Кратко опишем процедуру ВПЦДТ. Производится поиск СПМВ на взвешенном графе . Запоминается начальная структура графа. Затем стягиваем в вершину каждый элемент покрытия . При стягивании в вершину выбирается ребро с минимальным весом соединяющим два элемента паросочетания .

После стягивания покрытых ребер в полученном графе применяется алгоритм . Получаем покрытие которое также выделяем. Далее, восстанавливается начальная структура графа с выделенными покрытиями и . Цепь длины три получается при объединении множества ребер принадлежащих и ().

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

АЛГОРИТМ

Вход: взвешенный предфрактальный граф .

Выход: покрытие простыми цепями длины три.

Шаг 1. Используя процедуру ПЦДТ последовательно для каждой затравки , найти покрытие простыми цепями длины три.

Шаг 2. На выходе шага 1 для каждой затравки получаем покрытий . Объединяя эти покрытия получим покрытие предфрактального графа

Процедура Выделения покрытия цепями длины три ребра (ПЦДТ).

Вход: взвешенный граф .

Выход: покрытие M простыми цепями длины три ребра.<

Теорема 8. Если существует покрытие, то алгоритм на предфрактальном -графе . выделяет покрытие .

Доказательство. С помощью процедуры ВПЦДТ осуществляется поиск цепей длины три ребра на подграф-затравках. Процедура ВПЦДТ основана на алгоритме Эдмондса.

Каждая вершина L-го ранга принадлежит какой-либо подграф-затравке , поскольку при построении предфрактального графа на шаге L все вершины замещаются затравкой . В результате все вершины, принадлежащие этой затравке, будут покрыты.

Поэтому алгоритм работает только на подграф-затравках L-го ранга

На подграф-затравке L-го ранга выделим покрытие В результате n вершин выделило покрытие . Далее выделим покрытие на второй затравке L-го ранга Выделилось еще n вершин в результате покрытия . Так как подграф-затравки и не связаны друг с другом, то это покрытие никак не влияет на .

Выделив покрытия на подграф-затравке , будет покрыто вершин.

На затравках выделялись покрытия , Таким образом, покрытием предфрактального графа является полученное покрытие. <

Теорема 9. Вычислительная сложность алгоритма , выделения покрытия цепями длины три (три ребра) на предфрактальном-графе , порожденного затравкой , где , , равна .

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

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

. <

Теорема 10. Алгоритм выделяет покрытие цепями длины три (три ребра) на предфрактальном (n,L)-графе , порожденном n-вершинной затравкой оптимальное по критерию , оцениваемое по критерию, и по критерию , если .

Доказательство. Минимизирует количество типов цепей критерий . Так как покрытие состоит только из цепей длины два ребра, то критерий принимает минимальное значение, а именно =1. Оценим мощность покрытия . Так как количество вершин на затравке равно n, то мощность покрытия на одной затравке равна . Алгоритм работает с подграф-затравками L-го ранга, а их , то . Оценим критерий По определению у взвешенного предфрактального граф коэффициент подобия и веса ребер L-го ранга будут принадлежать интервалу . Пусть выделенное покрытие включает в себя ребра самых больших весов тогда вес покрытия будет равен

.

Литература

1. Kshemkalyani A.D. Distributed Computing Principles, Algorithms, and Systems / A. D. Kshemkalyani, M. Singhal // Cambridge University Press, 2008. - 754 p.

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

3. Кристофидес Н. Теория графов. Алгоритмический подход / Н. Кристофидес. - М.: Мир, 1978. - 432 с.

4. Перепелица В. А. Многокритериальные модели и методы для задач оптимизации на графах / В. А. Перепелица // LAP LAMBERT Academic Publication, 2013. - 333 с.

5. Павлов Д. А. Особенности многокритериальной оптимизации на предфрактальных графах: задача покрытия простыми цепями : монография / Д. А. Павлов. - Краснодар : КубГАУ, 2016. - 122 с.

6. Павлов Д. А. Многокритериальная задача покрытия предфрактального графа простыми цепыми : дис. … канд. физ.-мат. наук (05.13.17) / Павлов Дмитрий Алексеевич; Таганрогский гос. радиотех. ун-т. - Таганрог, 2004. - 110 с.

7. Павлов Д. А. Алгоритмы с оценками построения покрытий непересекающимися простыми цепями на предфрактальном графе / Д. А. Павлов // Препринт Спец. астрофиз. обсерватории РАН. Нижний Архыз, 2004. - №199. - 24 с.

8. Павлов Д. А. Об одной многокритериальной задаче выделения наибольших максимальных цепей на предфрактальных графах / Д. А. Павлов // Препринт Спец. астрофиз. обсерватории РАН. Нижний Архыз, 2004. - № 198. - 15 с.

9. Павлов Д. А. Многокритериальная задача выделения маршрутов на предфрактальном графе / Д. А. Павлов, С. И. Салпагаров // Известия ТРГУ. - Таганрог : ТРГУ, 2004. - №8 (43). - С. 303-304.

10. Павлов Д. А. Математическая модель системы управления корпоративной сети с распределенной вычислительной системой / Д. А. Павлов // Наука сегодня : материалы VII Междунар. науч.-практ. конф. - Вологда : ООО «Маркер», 2015. - С. 129-130.

11. Павлов Д. А. Мера сходства предфрактальных графов / Д. А. Павлов // Параллельная компьютерная алгебра и её приложения в новых инфокоммуникационных системах : сб. науч. тр. I Междунар. конф. - Ставрополь : Изд.-информ. центр «Фабула», 2014. - С. 81-86.

12. Лихобабин Е.Г. Моделирование транспортной сети на предфрактальных графах // Глобализация науки: проблемы и перспективы : сб. статей Междунар. науч.-практ. конф. - Уфа : РИО МЦИИ Омега Сайнс, 2015. - С. 3-6.

13. Узденов А.А., Павлов Д.А. Об одной многокритериальной задаче о р-медианах на предфрактальных графах// Электронный научный журнал "Исследовано в России". -- 2007. -- Т. 10. --с.1953.

14. Павлов Д. А. Оценка покрытия предфрактального графа кратчайшими простыми цепями / Д. А. Павлов // Математическое моделирование и компьютерные технологии : материалы VI Всерос. симпозиума. - Кисловодск : КИЭП, 2004. - С. 15-16.

15. Павлов Д. А. Алгоритмы определения абсолютных р-центров на предфрактальных графах с затравкой полный n-вершинный граф / Д. А. Павлов // Препринт Спец. астрофиз. обсерватории РАН. Нижний Архыз, 2004. - № 201. - 7 с.

16. Павлов Д. А. Об одной многокритериальной задачи покрытия минимального веса предфрактального графа простыми пересекающимися цепями / Д. А. Павлов // Препринт Спец. астрофиз. обсерватории РАН. Нижний Архыз, 2004. - № 200. - 10 с.

17. Павлов Д. А. Многокритериальная задача покрытия фрактальных и предфрактальных графов простыми цепями / Д. А. Павлов - Черкесск : КЧГТА, 2004. - 12 с. Рукопись деп. в ВИНИТИ, №1248-В2004.

18. Павлов Д. А. Многокритериальная задача покрытия предфрактального графа цепями типа / Д. А. Павлов - Черкесск : КЧГТИ, 2003. - 17 с. Рукопись деп. в ВИНИТИ, №670-В2003.

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