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

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

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

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

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

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

группы А-13-08

Буренков Сергей

проверил Панков

Николай Александрович

Москва, 2012

Введение

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

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

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

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

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

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

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

2. генерация всех возможных перестановок из n элементов, где n – количество вершин графов;

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

4. При обнаружении хотя бы одного совпадения в п. 3 можем сделать вывод, что графы изоморфны. Если после перебора совпадения не установлено, вывод – графы не изоморфны.

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

Заметим, что с ростом количества вершин сравниваемых графов растет число вариантов, причем их количество составляет . Имеет смысл реализовывать параллельно п. 3, так как в нем а) операции независимы; b) собрана бОльшая часть вычислений.

Результаты вычислительного эксперимента

Входными данными служат 2 графа из 12 вершин. Задаются матрицами смежности. Количество изоморфных графов для графа из 12 вершин достаточно велико: . Поэтому не удалось получить решение для графов из 12 вершин и выше из-за лимита на временные ресурсы и память.