Лабораторные работы / Лабораторная работа 4 / Проверка изоморфности пары графов (Сержанов)
.docxНациональный исследовательский университет
«Московский энергетический институт»
Лабораторная работа №4
по дисциплине «Параллельные системы и параллельное программирование»
Проверка изоморфности пары графов с использованием нитевого распараллеливания
выполнил студент
группы А-13-08
Сержанов Никита
проверил Панков Н.А
Москва, 2012
Введение
В теории графов изоморфизмом невзвешенных и неориентированных графов и называется биекция между множествами вершин графов такая, что любые две вершины uи vграфа Gсмежны тогда и только тогда, когда вершины и смежны в графе H. Биекцию fзаписывают в виде подстановки изоморфизма
Постановка задачи
Имеется пара графов, заданных количеством вершин и матрицами смежности. Требуется определить, являются ли графы изоморфными.
Последовательный алгоритм
Графы Gи Hявляются изоморфными, если путем перестановки строк и столбцов матрицы смежности графа Gудается получить матрицу смежности графа H.
Этапы последовательного решения:
-
инициализация входных данных (графы с разным числом вершин заведомо не могут быть изоморфными);
-
генерация всех возможных перестановок
-
По полученным перестановкам из матрицы смежности графа Gполучаем матрицы смежностей всех возможных графов, изоморфных графу G. Каждую полученную матрицу сравниваем с матрицей смежности H.
-
При обнаружении хотя бы одного совпадения в п. 3 можем сделать вывод, что графы изоморфны. Если после перебора совпадения не установлено, вывод – графы не изоморфны.
Параллельный алгоритм
Реализуем параллельно п. 3, так как в нем большая часть вычислений.
Результаты вычислительного эксперимента
10 вершин 11 вершин
t(c) t(c)
4.70 |
|
|
1021.23 |
|
|
1 |
2.96 |
1.58 |
|
674.32 |
1.51 |
|
2 |
1.59 |
2.95 |
|
433.87 |
2.35 |
|
3 |
1.19 |
3.94 |
|
271.54 |
3.76 |
|
4 |
Зависимость ускорения от числа исполнителей