Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Лабораторные работы / Лабораторная работа 4 / Проверка изоморфности пары графов (Сержанов)

.docx
Скачиваний:
25
Добавлен:
28.06.2014
Размер:
32.68 Кб
Скачать

Национальный исследовательский университет

«Московский энергетический институт»

Лабораторная работа №4

по дисциплине «Параллельные системы и параллельное программирование»

Проверка изоморфности пары графов с использованием нитевого распараллеливания

выполнил студент

группы А-13-08

Сержанов Никита

проверил Панков Н.А

Москва, 2012

Введение

В теории графов изоморфизмом невзвешенных и неориентированных графов и называется биекция между множествами вершин графов такая, что любые две вершины uи vграфа Gсмежны тогда и только тогда, когда вершины и смежны в графе H. Биекцию fзаписывают в виде подстановки изоморфизма

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

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

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

Графы Gи Hявляются изоморфными, если путем перестановки строк и столбцов матрицы смежности графа Gудается получить матрицу смежности графа H.

Этапы последовательного решения:

  1. инициализация входных данных (графы с разным числом вершин заведомо не могут быть изоморфными);

  2. генерация всех возможных перестановок

  3. По полученным перестановкам из матрицы смежности графа Gполучаем матрицы смежностей всех возможных графов, изоморфных графу G. Каждую полученную матрицу сравниваем с матрицей смежности H.

  4. При обнаружении хотя бы одного совпадения в п. 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

Зависимость ускорения от числа исполнителей