Участник:Full/Поиск автоморфизмов графов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ \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]\displaystyle{ g^s_k }[/math] фиксирует [math]\displaystyle{ r_1, \ldots r_k }[/math], то структура останется измененой, что означает отображение не будет являться автоморфизмом.

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

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

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

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

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

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

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

Вычислительным ядром алгоритма является последовательность множеств [math]\displaystyle{ M'_1 \ldots M'_n }[/math]. Вычисляется на основе соответствующих [math]\displaystyle{ M_1 \ldots M_n }[/math]. Построение [math]\displaystyle{ M_1 \ldots M_n }[/math] занимает не существенную часть времени.

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

Каждое множество [math]\displaystyle{ M_i (i = 2 \ldots n) }[/math] вычисляется из [math]\displaystyle{ M'_{i-1} }[/math] путем добавления в каждый элемент (частичная перестановка, представленная вектором целых чисел) из [math]\displaystyle{ M'_{i-1} }[/math] всех возможных оставшихся чисел, которых нет в соответствующем элементе.

Для этого удобно использовать 2 не фиксированных по количеству строк двумерных массива размера t на n (t может увеличиваться), хранящих частичные отображения, такого вида:

[math]\displaystyle{ \begin{pmatrix} a_{11} & a_{12} & \ldots &a_{1i} & ? & \ldots & ? \cr a_{21} & a_{22} & \ldots &a_{2i} & ? & \ldots & ? \cr \ldots \cr a_{k1} & a_{k2} & \ldots &a_{ki} & ? & \ldots & ? \cr ? & ? & \ldots &  ? & ? & \ldots & ? \cr \ldots \cr ? & ? & \ldots &  ? & ? & \ldots & ? \cr \end{pmatrix} }[/math]

? - эти значения не известны и заполняются постепенно.

Один массив для [math]\displaystyle{ M'_{i-1} }[/math], другой для вычисления из предыдущего [math]\displaystyle{ M_i }[/math]. Из каждой строки множества [math]\displaystyle{ M'_{i-1} }[/math] (первый массив), в соответствие с алгоритмом, получается [math]\displaystyle{ n }[/math] новых строк длины i, которые записываются во второй массив (расширяется, если нужно).

После этого, второй массив копируется в первый и запускается цикл по всем векторам. Вектор исключается из массива, если [math]\displaystyle{ a_{ji} }[/math] равен какому-либо числу в данном векторе или вектор с [math]\displaystyle{ a_{ji} }[/math] является частичной перестановкой, не удовлетворяющей критерию;

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

Схема реализации представлена на языке C++

#define GRAPH_SIZE 300
#define ROW_ARR_SIZE 10000 
#define COL_ARR_SIZE GRAPH_SIZE

const int N = GRAPH_SIZE;

vector<array<unsigned short,COL_ARR_SIZE>> Mi(ROW_ARR_SIZE, COL_ARR_SIZE);
vector<array<unsigned short,COL_ARR_SIZE>> M'i(ROW_ARR_SIZE, COL_ARR_SIZE);
unsigned char **matrix;

struct_M'i make_M'i(Mi) {
    struct_M'i M'i;
    for (auto x: Mi) {
        for (int i = 0; i < n; ++i) {
            if (check_h(x) && !eq(x, i)) {
                M'i.push_back(x.add(i));
            }
        }
    }
    return M'i;
}

struct_Mi make_Mi(M'i) {
    struct_Mi Mi;
    for (auto x: M'i) {
        for (int i = 0; i < n; ++i) {
           Mi.push_back(x.add(i));
        }
    }
    return Mi;
}

int main() {

    //заполнение матрицы смежности
    init_automorphisms(matrix);

    //распараллеливание
    switch(process) {
    case 0:
        begin = 0;
        end = stop_0;
    case 1:
        begin = start_1;
        end = stop_1;
    ...
    case N:
        begin = start_n;
        end = M_0.size();

    //основной цикл
    for (i = begin; i < end; ++i) {
        Mi = make_Mi(M'i-1);
        M'i = make_M'i(Mi);
    }

    //сохранение результата (вывод автоморфизмов)
    final_automorphism(M'i);
}

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

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

Информация о реализациях данного алгоритма не найдена. При анализе алгоритма было разработано 2 программы:

1) приложение с графическим интерфейсом, написанное на Qt

• не поддерживает распараллеливание
• справляется с графами размера до 500 вершин
• удобный анализ графов
• помимо нахождения автоморфизмов, решает задачи изоморфизма и гомоморфизма графов

2) программа на языки C++ с поддержкой OpenMPI

• поддерживает распараллеливание средствами OpenMPI
• помимо нахождения автоморфизмов, сохраняет много информации для анализа графов с большим количеством вершин