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




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

Файл
4249-1.rtf
27229-1.rtf
137744.rtf
80822.rtf
161930.rtf




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