Параллельный алгоритм нахождения достижимостей в графе

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 681. 3
ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ НАХОЖДЕНИЯ ДОСТИЖИМОСТЕЙ В ГРАФЕ Князькова А. В., Волченская Т. В., Князьков В. С.
ФГБОУ ВПО «Вятский государственный университет», Киров, e-mail: kniazkov@list. ru
Приводятся области применения задач на графах и сетях, в которых используется понятие достижимости. Операция построения матрицы достижимости является ключевой в задаче разбиения графа на максимальные сильно связные подграфы, в задаче построения кратчайших путей и в ряде других задач. Рассматриваются способы представления графовых моделей для компьютерной обработки. Приводится понятие достижимости и представление его через многозначные отображения и транзитивные замыкания. Рассматривается параллельный алгоритм нахождения матрицы достижимости, главной особенностью которого является то, что операция построения матрицы достижимостей может быть выполнена параллельно для всех вершин графа. Количество итераций зависит не от размерности графа, а от его структуры, а именно от длины простых цепей и контуров. В реальных сетевых моделях, где велика степень связности графа, скорость построения матрицы еще более возрастет.
Ключевые слова: граф, графовая модель, достижимость в графах, матрица достижимости, параллельный алгоритм
PARALLEL ALGORITHM OF SEARCH ACCESSIBILITY IN THE GRAPH Knyazkova A.V., Volchenskaya T.V., Knyazkov V.S.
Vyatka State University, Kirov, e-mail: kniazkov@list. ru
There are problems in the field of graph and network tasks in which the concept of reachability is used. The operation of reachability matrix construction is the key point in the problem of graph splitting up into maximal coherent subgraphs in a shortest construction problem and in a number of other problems. Many ways of performance graph models for computer processing are considered. The concept of reachability and its performance through multiple-valued displays and transitive short circuits is presented. The parallel algorithm is used to create the reachability matrix to be considered. The main characteristic is that construction of a reachability matrix operation can be executed in parallel for all graph nodes. The quantity of iterations depends on its structure, not the graph dimensions. It depends on simple circuits and paths. In real network models where the degree of connectivity in the graph is large, the speed of the construction of a matrix will increase.
Keywords: graph, graph model, accessibility in the graph, a matrix of the accessibility, parallel algorithm
Сетевые и графовые модели охватывают довольно широкий класс задач, встречающихся при проектировании систем, планировании работ, распределении продукции, организации транспортных перевозок,
размещении различных центров обслуживания и т. п.
Задач, в которых используется понятие достижимости, довольно много. Вот одна из них. Граф может быть моделью какой-то организации или социальной сети, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лица х. быть передана другому лицу х, т. е. существует ли путь, идущий от вершины х. к вершине х. Если такой путь существует, то говорят, что вершина х. достижима из вершины х Можно интересоваться достижимостью вершины х. из вершины х. только на таких путях, длины которых не превосходят заданной величины или длина которых меньше наибольшего числа вершин в графе и т. п. задачи.
Характерной особенностью таких задач является большая размерность, что обуслов-
ливает необходимость конструирования более скоростных алгоритмов. Плодотворной основой для построения таких алгоритмов могут служить их сетевые и графовые формализации [1, 7].
Программные реализации указанных задач весьма универсальны и просто программируемы при небольших размерностях графа. Однако при значительном увеличении количества узлов или дуг графа время программного решения при последовательном исполнении инструкций становится практически неприемлемым. Аппаратные реализации хотя и обеспечивают необходимую скорость за счет параллельной обработки информации, но не обладают достаточной алгоритмической гибкостью, в силу этого — их адаптация к изменениям логики вычислений не всегда возможна [2, 3, 4, 5]. Решением данной проблемы является использование таких вычислительных алгоритмов, которые бы совмещали скорость аппаратных вычислений с легкостью программной модификации в параллельных алгоритмах [6, 8, 9].
В рассматриваемых алгоритмах графы заданы с помощью матрицы смежности,
которая дает его компактное представление, особенно если есть возможность работать с двоичными битами в машинном слове. Анализ алгоритмов решения оптимизационных задач на графах приводит к выводу. что большинство операций на графах могут выполняться параллельно для каждой из
вершин. что позволяет значительно ускорить обработку данных.
Допустим, что мы имеем граф, структура которого описана матрицей смежности (рис. 1) размерностью пХп, (где п — число вершин графа), однозначно представляющая его структуру:
*1 Х2 *3 Х4 Х5 Х6 Х1
*1 1 1 0 0 1 0 0
*2 0 1 0 1 0 0 0
*3 0 0 1 1 0 0 0
х4 0 0 0 1 1 0 0
*5 0 0 0 0 1 0 0
*6 0 0 1 0 0 1 1
х7 0 0 0 1 0 1 1
б
Рис. 1. Пример 1: а — граф- б — матрица смежности графа
А = {а. }, /,. = 1, 2, …, п, а каждый эле-
У
мент матрицы определяется следующим образом:
а. = 1, если существует дуга из вершины х. в вершину х,
а. = 0, если нет дуги из вершины х. в вершину х.
Достижимость в графе описывается матрицей достижимости
Я = [г ], /'-,. = 1, 2, … п, где п — число вершин графа, а каждый элемент определяется следующим образом:
г. = 1, если вершина х. достижима из х. ,
г. = 0, в противном случае.
Множество вершин Я (х.) графа О, достижимых из заданной вершины х состоит из таких элементов х, для которых (/, у)-й
элемент в матрице достижимостей равен 1. Очевидно, что все диагональные элементы в матрице Я равны 1, поскольку каждая вершина достижима из себя самой путем длины 0. Поскольку прямое отображение 1-го порядка Г+1 (х.) является множеством таких вершин х, которые достижимы из х. с использованием путей длины 1, то множество Г+(Г+1(х.)) = Г+2 (х.) состоит из вершин, достижимых из х. с использованием путей длины 2. Аналогично Г+^х.) является множеством вершин, которые достижимы из х. с помощью путей длины p.
Так как любая вершина графа, которая достижима из х должна быть достижима с использованием пути (или путей) длины 0 или 1, или 2, …, или p, то множество вершин, достижимых для вершины х можно представить в виде
R (x.) = {х. } и Г+1 (х.) и Г+2(х.) и … и Г+^х.).
Как видим, множество достижимых вершин R (x.) представляет собой прямое транзитивное замыкание вершины х т. е. R (x.) = T+(x.). Следовательно, для построения матрицы достижимости находим достижимые множества R (x.) для всех вершин х е X. Полагая г. = 1, если х е R (x) и г = 0. …. . в противном случае.
Суть предлагаемого параллельного алгоритма нахождения матрицы достижимости заключается в следующем:
1. Так как каждая вершина достижима сама для себя, то в матрице достижимости R1 на главной диагонали должны стоять 1. Единицы можно предварительно занести на главную диагональ матрицы смежности, для того чтобы в п. 2 алгоритма использовать общую формулу преобразования.
М атрица R1
Xi X 2 X З X 4 X 5 x б X Т
x i i i 0 i i 0 0
X 2 0 i 0 i i 0 0
X З 0 0 i i i 0 0
X 4 0 0 0 i i 0 0
X 5 0 0 0 0 i 0 0
X б 0 0 i i i i i
X Т 0 0 i i i i i
M атрица R2
x i X 2 X З X 4 X 5 x б x Т
x i i i 0 i i 0 0
X 2 0 i 0 i i 0 0
X З 0 0 i i i 0 0
X 4 0 0 0 i i 0 0
X 5 0 0 0 0 i 0 0
x б 0 0 i i i i i
x Т 0 0 i i i i i
2. По матрице смежности для каждой вершины графа х. находим строку в матрице Я1 как результат логического сложения тех (-х) строк матрицы смежности, для которых х. = 1
УК- = А-| *(^115 ^12513' •& quot-
УА,.2 Х^., ^22? -^23' & quot-^2п
ХС^и1'А12' А|3' Дш) —
Например, для вершины х1 в матрице смежности элементы, а а12 и а15 равны 1, следовательно, строка в матрице R1 для вершины х1 будет получена как результат логического сложения элементов соответствующих позиций первой, второй и пятой строк матрицы смежности.
Операция построения матрицы достижимостей № может быть выполнена параллельно для всех вершин графа.
3. По матрице R1 для каждой вершины графа находим матрицу следующего уровня R2 по аналогичным формулам:
… <-)у
… КЛ
4. Далее процедура построения матрицы достижимости
R*
по матрице достижимости предыдущего уровня Я*-1 повторяется до тех пор, пока RA: не будет равной Rt-1.
В нашем примере на рис. 1 построение матрицы достижимости произошло за одну итерацию, так как R2 = R1.
Количество итераций зависит от структуры графа, а именно от длины простых цепей и контуров. Рассмотрим второй пример, показанный на рис. 2. Как видим из примера, матрица достижимости строится за три итерации, то есть только R4 = R3. Таким образом, количество итераций равно длине самой длинной простой цепи и не зависит от количества вершин графа. В реальных сетевых моделях, где велика степень связности графа, скорость построения матрицы еще более возрастет.
Х2
*3
XI
Х2
Х3
Х4
Х5 Х6
XI
Х8
х4
Х
хг
Хз
Х4
х5
Хб
Х1
X
1 1 0 1 0 0 0 0
0 1 1 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 1
Рис. 2. Пример 2: а — граф- б — матрица смежности графа
В FUNDAMENTAL RESEARCH № 5, 20i4 В
б
а
Матрица R1
X1 X 2 X 3 X 4 X 5 x б X 7 X 8
x 1 1 1 1 1 1 0 0 0
X 2 0 1 1 1 0 0 0 0
X 3 0 0 1 1 1 0 0 0
X 4 0 0 0 1 1 1 0 0
X 5 0 0 0 0 1 1 0 1
X б 0 0 0 0 0 1 0 1
X 7 0 0 0 0 0 1 1 1
X 8 0 0 0 1 1 1 0 1
Матрица R3
X1 X 2 X 3 X 4 X 5 x б X 7 X 8
x 1 1 1 1 1 1 1 0 1
X 2 0 1 1 1 1 1 0 1
X 3 0 0 1 1 1 1 0 1
X 4 0 0 0 1 1 1 0 1
X 5 0 0 0 0 1 1 0 1
x б 0 0 0 0 0 1 0 1
X 7 0 0 0 0 0 1 1 1
X 8 0 0 0 1 1 1 0 1
Матрица R2
x 1 X 2 X 3 X 4 X 5 x б X 7 X 8
x 1 1 1 1 1 1 1 0 1
X 2 0 1 1 1 1 1 0 0
X 3 0 0 1 1 1 1 0 1
X 4 0 0 0 1 1 1 0 1
X 5 0 0 0 0 1 1 0 1
x б 0 0 0 0 0 1 0 1
X 7 0 0 0 0 0 1 1 1
X 8 0 0 0 1 1 1 0 1
Матрица R4
x 1 X 2 X 3 X 4 X 5 x б X 7 X 8
x 1 1 1 1 1 1 1 0 1
X 2 0 1 1 1 1 1 0 1
X 3 0 0 1 1 1 1 0 1
X 4 0 0 0 1 1 1 0 1
X 5 0 0 0 0 1 1 0 1
x б 0 0 0 0 0 1 0 1
X 7 0 0 0 0 0 1 1 1
X 8 0 0 0 1 1 1 0 1
По сравнению с последовательным алгоритмом, в котором время выполнения зависит от размерности графа, предлагаемое решение позволяет значительно увеличить быстродействие.
Операция построения матрицы достижимости является ключевой в задаче разбиения графа на максимальные сильно связные подграфы, в задаче построения кратчайших путей и в ряде других задач.
Список литературы
1. Волченская Т В. Разработка алгоритмов решения задач на графах с применением клеточной логики // Новые информационные технологии и системы: тез. докл. II меж-дунар. научн. техн. конф. октябрь 1996 г., г. Пенза. — Пенза, 1996. — С. 95−96.
2. Волченская Т. В., Князьков В. С. и др. Устройство для определения числа вершин подграфов графа. Авт. св. № 1341б49 G06F'-5/20, БИ № Зб, 1987.
3. Волченская Т. В., Князьков В. С. и др. Устройство для исследования подмножеств графа. Авт. св. № І4І005І, G06F15/31, БИ № 2б, 1988.
4. Волченская Т. В., Князьков В. С. и др. Устройство для исследования графов. Авт. св. № 13б3237, G06F15/20, БИ № 48, 1987.
5. Волченская Т. В., Князьков В. С. и др. Многофункциональная ячейка однородной структуры. Патент .№ 1бб3б09, G06F7/00, октябрь 1993.
6. Волченская Т. В., Князьков В. С. Спецпроцессоры для решения задач на графах // Научный журнал Advanced science № З, ПРИП ФгБОУ ВПО «ВятГу». — Киров, 2013. — С. 73−82.
7. Кристофидес Н. Теория графов. Аналитический подход. — М.: Мир, 1978.
8. Knyaz’kov V.S., Volchenskaya T.V. Maximally Parallel Algorithms for Raster Image Processing by Cellular VLSI Processors // Pattern Recognition and Image Analysis. -1996. — Vol. 6, № 2. — P. 403−404.
9. Knyaz’kov VS. An Assotiative Cellular VLSI Processor for Paralled Processing by Raster Image: the concept and Applied Computations // Pattern Recognition and Image Analysis. -1996. — Vol. 6, № 2. — P. 401−402.
References
1. Volchenskaya T.V. Tezisy dokladov II Mezhdunarodnoin-
auchno- teshnicheskoikonferenci i «Novyeinformacionnietesh-
nologiisistemy» (Theses of reports of II international scientifically — technical conference «New information technologies and systems»), October 1996, Penza, pp. 95−96.
2. Volchenskaya T.V., Knyazkov VS. The device for definition of number of tops of subgraphs the graph. The copyright certificate no. 1 341 649 G06F15/20, the bulletin of inventions no. 36, 1987.
3. Volchenskaya T.V., Knyazkov VS. The device for research of subsets the graph. The copyright certificate no. 1 410 051, G06F15/31, the bulletin of inventions no. 26, 1988.
4. Volchenskaya T.V., Knyazkov VS. The device for research the graph. The copyright certificate no. 1 363 237, G06F15/20, the bulletin of inventions no. 48, 1987.
5. Volchenskaya T.V., Knyazkov V.S. Multipurpose cell of homogeneous structure. The patent no. 1 663 609, G06F7/00, 1993.
6. Volchenskaya T.V., Knyazkov V.S. The specialized processors for the decision of problems on graphs. Journal of Advanced science no. 3, 2013, pp. 73−82.
7. Kristofides N. Graph theory. The analytical approach. Moscow, 1978.
8. Knyaz’kov V.S., Volchenskaya T.V. Maximally Parallel Algorithms for Raster Image Processing by Cellular VLSI Processors // Pattern Recognition and Image Analysis, Vol. 6, no. 2, 1996, pp. 403−404.
9. Knyaz’kov V.S. An Assotiative Cellular VLSI Processor for Paralled Processing by Raster Image: the concept and Applied Computations // Pattern Recognition and Image Analysis, Vol. 6, no. 2, 1996, pp. 401−402.
Рецензенты:
Шатров А. В., д.ф. -м.н., профессор, зав. кафедрой «Математическое моделирование в экономике» Вятского государственного университета, г. Киров-
Бутаев М. М., д.т.н., профессор, ученый секретарь ОАО «НПП Рубин», г. Пенза.
Работа поступила в редакцию 26. 02. 2014.

ПоказатьСвернуть
Заполнить форму текущей работой