Алгоритм Ульмана: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 43: Строка 43:
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
  
Последовательная сложность алгоритма:
 
  
 
• полиномиальная, для фиксированного графа <math>H</math>
 
• полиномиальная, для фиксированного графа <math>H</math>

Версия 19:50, 18 ноября 2016

Содержание

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

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

Алгоритм Ульмана[1][2] решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом

  • для фиксированного графа [math]H[/math] время полиномиальное;
  • для планарного графа [math]G[/math] время работы линейное (при фиксированном графе [math]H[/math]).

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

Пусть задан ориентированный граф [math]G=(V,E)[/math] с вершинами [math]V= ( v_1,v_2,...,v_n)[/math] и рёбрами [math]E=(e_1,e_2,...,e_m)[/math] , и ориентированный граф [math]H=(W,F)[/math] с вершинами [math]W=(w_1,w_2,...,w_n)[/math] и рёбрами [math]F=(f_1,f_2,...,f_m)[/math]. Булевы функции [math]p(v_i,w_j )[/math] и [math]q(e_i,f_j )[/math] задают совместимость вершин и рёбер двух графов (например, что вершины помечены одним и тем же химическим элементом).

Подграф [math]G'=(V',E' )[/math] графа [math]G[/math] изоморфен графу [math]H[/math], если существует взаимно-однозначное отображение [math]\varphi:V' \rightarrow W[/math], удовлетворяющее условиям:

1. [math]p(v, \varphi(v))[/math] истинно для всех вершин [math]v \in V'[/math].

2. Если вершины [math]v_1,v_2 \in V'[/math] и [math]e=(v_1,v_2 ) \in E[/math], то [math]e \in E' [/math] и существует соответствующее ребро [math]f=( \varphi (v_1 ), \varphi (v_2 )) \in F[/math].

3. [math]q(e,f)[/math] истинно.

Задача поиска изоморфных подграфов состоит в отыскании подграфов графа [math]G[/math], изоморфных графу-шаблону [math]H[/math].

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

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

Определим булеву матрицу [math]B= ( B_{i,j} )[/math] размера следующим образом:

[math]B_{i,j}[/math] истинно, если не исключена возможность того, что [math]\varphi(v_i )=w_j[/math];

[math]B_{i,j}[/math] ложно в противном случае.

Алгоритм Ульмана состоит в последовательном уточнении матрицы до тех пор, пока такое уточнение возможно. После остановки алгоритма матрица либо целиком состоит из нулей, либо содержит информацию обо всех возможных изоморфных подграфах.

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

1. Этап инициализации.

a. [math]B_(i,j):=p(v_i,w_j )[/math].

b. [math]B_(i,j):=0[/math], если степень вершины [math]v_i[/math] меньше степени вершины [math]w_j[/math] (таким образом, вершина [math]v_i[/math] заведомо не может соответствовать вершине [math]w_j[/math]).

c. [math]B_(i,j):=0[/math], если есть другие основания полагать, что вершина [math]v_i[/math] не может соответствовать вершине [math]w_j[/math] (например, с учётом функции [math]q[/math]).

2. Основной шаг. Пусть [math]B_(i,j):=1[/math]. Выполним поиск от вершины [math]v_i[/math], принимая во внимание текущее состояние матрицы [math]B[/math] и функцию [math]q[/math]. В результате либо будет найден изоморфный подграф, либо будет доказано, что вершина [math]v_i[/math] не может соответствовать вершине [math]w_j[/math]. В последнем случае производится присваивание [math]B_(i,j):=0[/math].

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

• полиномиальная, для фиксированного графа [math]H[/math]

• линейная, для фиксированного графа [math]H[/math] и планарного графа [math]G[/math].

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

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

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

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

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

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

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

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

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

2.4.1 Масштабируемость алгоритма

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

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

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

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

3 Литература

  1. Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.
  2. Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.