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

Посмотреть архив целиком

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

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

















Лабораторная работа №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





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




Случайные файлы

Файл
104344.rtf
ref-16044.doc
132286.rtf
REF_ZOL.DOC
18852-1.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.