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

Московский Энергетический Институт (Технический Университет)

Институт автоматики и вычислительной техники

Кафедра Прикладной математики

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

по дисциплине:

Параллельные системы

тема: «Задачи на графах»

вариант №5 – «Поиск автоморфизмов графа»

Выполнил:

Бочаров Иван Андреевич

Проверил:

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

Москва

2012 г.

Введение

Дадим определение основному понятию, используемому в данной работе – понятию автоморфизма графа. Сперва рассмотрим неориентированный граф без петель.

Автоморфизм графа – произвольная подстановка на множестве вершин графа, сохраняющая отношение смежности, т.е. такова, что образы и вершин и смежны тогда и только тогда, когда смежны сами вершины u и v. Следует заметить, что очевидным образом это определение можно распространить на случай взвешенного ориентированного графа без петель – перестановка помимо отношения смежности должна сохранять веса рёбер между смежными вершинами.

Известно, что множество автоморфизмов графа образует группу с операцией композиции в качестве операции умножения.

Очевидно, что каждый граф имеет хотя бы один автоморфизм – тривиальную подстановку . По этой причине для нас интерес представляют только нетривиальные автоморфизмы. Граф, для которого единственный возможный автоморфизм – это тождественное отображение, называется асимметрическим.

Метод решения

На данный момент не существует эффективного алгоритма поиска автоморфизмов графа. Все имеющиеся на сегодняшний день алгоритмы являются модификациями полного перебора (метод ветвей и границ и т.п.).

В данной работе используется полный перебор. Граф представляется матрицей смежности ( – вес ребра из вершины в вершину ). Для каждой нити параметром служит структура, несущая в себе информацию о числе подстановок, которое необходимо проверить, и об индексе перестановки, с которой нить должна начинать проверку на принадлежность к группе автоморфизмов графа. Также в поля этой структуры записывается результат – количество автоморфизмов, принадлежащих подмножеству множества подстановок, проверенных нитью, и их индексы.

При запуске нити по индексу определяется начальная перестановка, а затем в цикле проверяются все перестановки. Следует заметить, что перестановки упорядочены в лексикографическом порядке.

Результаты

Основные результаты были получены при тестировании разработанной программы на так называемых полных графах. Очевидно, что в полных графах группа автоморфизмов графа совпадает с множеством всех подстановок графа и имеет мощность , где – количество вершин графа. В связи с так называемым комбинаторным взрывом решение задачи поиска автоморфизмов графа может занимать значительное время.

Для каждого графа и количества нитей время было измерено 5 раз и в качестве конечного значения была выбрана медиана полученного множества.

Испытания проводились на стенде со следующей конфигурацией:

CPU: Intel Core i5 2500 МГц Ivy Bridge (3210M)

Количество ядер: 2 физических, 4 виртуальных

Кэш: 3 Mb L2 (L3) Cache

RAM: 4096 Мб DDR3-1600МГц

ОС: MS Windows 7 Home Basic x64

Таблица результатов (время в секундах):

Ускорение