Участник:Full/Поиск автоморфизмов графов
Алгоритм: Поиск автоморфизмов графов
Автор статьи: Ефремов С.С. группа 419
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
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] является множеством всех возможных автоморфизмов (или пустое, если их нет).
