Участник:Full/Поиск автоморфизмов графов: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 1: Строка 1:
 +
Алгоритм: Поиск автоморфизмов графов
 +
Автор статьи: Ефремов С.С. группа 419
  
 
= Свойства и структура алгоритмов =
 
= Свойства и структура алгоритмов =

Версия 17:32, 30 октября 2017

Алгоритм: Поиск автоморфизмов графов Автор статьи: Ефремов С.С. группа 419

1 Свойства и структура алгоритмов

Данный алгоритм, описанный в статье Егорова В.Н.[1], предназначен для поиска автоморфизмов графов, которые можно представить в виде матриц смежности, а также для исследования изоморфности графов. Так как алгоритм работает с матрицами, можно решать эти же задачи и на других комбинаторных объектах, представимых матрицами смежности[2].

1.1 Общее описание алгоритма

На вход подается матрица смежности графа. При отображение вершины v1 в вершину v2 в соответсвующей графу матрице меняются местами строка и столбец v1 со строкой и столбцом v2. Автоморфизмом является отображение множества вершин графа на себя, сохраняющее смежность. Это есть такая перестановка строк и столбцов матрицы, после применения которой, матрица останется той же.

1.2 Математическое описание алгоритма

1.2.1 Определения и обозначения

[math]A = A^{n\times n}[/math] - матрица смежности графа [math]G(V,E)[/math] размера [math]n\times n[/math]; [math]a_{ij}[/math] - элементы матрицы ,[math]\ i,j = 1,\ldots,n=|V|[/math].

Частичным отображением [math]g^s_k[/math] ([math]s[/math] - обозначает индекс элемента в множестве [math]M_k[/math]) называется подстановка вида

[math] \begin{pmatrix} 1 & 2 & \ldots & k & k+1 &\ldots & n\cr r_1 & r_2 & \ldots & r_k & q_{k+1} & \ldots & q_n \end{pmatrix} [/math]

, где [math]r_1,\ldots,r_k[/math] - фиксированные (заданные) элементы, [math]q_{k+1},\ldots,q_n[/math] - произвольные, причем последовательность [math]r_1,\ldots,r_k[/math], [math]q_{k+1},\ldots,q_n[/math] является перестановкой вершин заданного графа.

[math]M_k[/math] - множество, состоящее из элементов [math]g^s_k[/math], [math]\ s = 1,\ldots,n_k=|M_k|[/math].

[math]|M_k|[/math] - количество элементов [math]g^s_k[/math] в множестве.

[math]M'_k[/math] - множество элементов, которые содержатся в [math]M_k[/math] и удовлетворяют критерию [math]h[/math].

h - критерий (описанный далее).

[math]\{M'_k\}[/math] - последовательность множеств [math]M'_k[/math], [math]k = 1,\ldots,n[/math].


1.2.2 Проверка по критерию

Критерием [math]h[/math] является проверка подматриц на равенство. Предположим, требуется определить, удовлетворяет ли элемент [math]g^s_k[/math] критерию h. Для этого необходимо, чтобы элементы [math]a_{ij}[/math], для всех [math]i,j \leq k[/math], были равны соответствующим элементам [math]a_{r_ir_j}[/math]. Подматрица [math]g^s_k[/math] выглядит так:

[math] \begin{matrix} & r_1 & r_2 & \dots & r_k \cr r_1 & a_{r_1r_1} & a_{r_1r_2} & \dots & a_{r_1r_k} \cr r_2 & a_{r_2r_1} & a'_{r_2r_2} & \dots & a_{r_2r_k} \cr \vdots & \vdots & \vdots & \ddots & \vdots \cr r_k & a_{r_kr_1} & a_{r_kr_2} & \dots & a_{r_kr_k} \cr \end{matrix} [/math]

Если хотя бы одно из равенств не выполнено, это означает, что по данной частичной подстановке хотя бы одна вершина отобразилась в другую так, что структура графа изменилась. А так как частичная перестановка [math]g^s_k[/math] фиксирует [math]r_1, \ldots r_k[/math], то структура останется измененой, что означает отображение не будет являться автоморфизмом.


1.2.3 Построение множеств частичных отображений

Описание построения [math]M'_n[/math].

На первом этапе рассматриваются все [math]g^s_1[/math], образующие множество [math]M_1[/math]. Каждый элемент [math]g^s_1[/math] проверяется по критерию h. Элементы, удовлетворяющие h, образуют [math]M'_1[/math]. В каждый элемент из [math]M'_1[/math] добавляется еще одно отображение (2 [math]\to[/math] [math]r_2[/math]), т.е. происходит переход от [math]g^s_1[/math] к [math]g^s_2[/math]. Из каждого [math]g^s_1[/math] получается разных [math](n-1)[/math] элементов [math]g^s_2[/math]. Всевозможные элементы [math]g^s_2[/math] образуют [math]M_2[/math]. Далее строится [math]M'_2[/math], добавляя в него только те элементы из [math]M_2[/math], которые удовлетворяют критерию. Аналогично получаются множества [math]M_3,\ M'_3,\ M_4,\ldots, M_n,\ M'_n[/math].


Таким образом, получается последовательнось множеств частичных отображенией:

[math]\{M'_k\}[/math]: [math]M'_1 \subseteq M'_2 \subseteq \ldots \subseteq M'_n[/math].

Множество [math]M'_n[/math] является множеством всех возможных автоморфизмов (или пустое, если их нет).

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Масштабируемость алгоритма и его реализации

2.4 Динамические характеристики и эффективность реализации алгоритма

2.5 Выводы для классов архитектур

2.6 Существующие реализации алгоритма

3 Литература

  1. Группы автоморфизмов и изоморфизм комбинаторных объектов и алгебраических структур. Егоров В.Н., Егоров А.В. (Ломоносовские чтения, Научная конференция, Москва, факультет ВМК МГУ имени М.В.Ломоносова).
  2. О группах автоморфизмов матриц. Егоров В.Н. (журнал "Прикладная дискретная математика").