Лабораторные работы / Лабораторная работа 2 / Проверка изоморфности пары графов (Буренков)

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

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

Лабораторная работа №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 вершин и выше из-за лимита на временные ресурсы и память.

	12 вершин			11 вершин			10 вершин			9 вершин
	время	ускорение	время		ускорение	время		ускорение	время		ускорение
1			304,97			23,21			1,91
4			88,41		3,45	6,97		3,33	0,59		3,24
8			90,39		3,37	7,1		3,27	0,62		3,08
12			66,01		4,62	5,17		4,49	0,47		4,06
16			55,65		5,48	4,46		5,20	0,41		4,66
20			46,93		6,50	3,77		6,16	0,37		5,16
24			41,68		7,32	3,44		6,75	0,38		5,03
28			37,93		8,04	3,23		7,19	0,36		5,31
32	2272,6		40,97		7,44	3,25		7,14	0,36		5,31
36	461,72		34,52		8,83	2,86		8,12	0,34		5,62
40	429,44		32,25		9,46	2,92		7,95	0,4		4,78
44	411,6		31,1		9,81	3,09		7,51	0,41		4,66
48	391,04		31,08		9,81	2,97		7,81	0,41		4,66
52	488,71		39,41		7,74	3,23		7,19	0,51		3,75
56	505,58		40,46		7,54	3,9		5,95	0,55		3,47
60	559,34		43,48		7,01	3,52		6,59	0,61		3,13
64	691,49		57,91		5,27	5,37		4,32	0,74		2,58