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

[непроверенная версия]

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

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
3 Литература

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

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

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

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

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

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

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

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

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

3. $q(e,f)$ истинно.

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

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

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

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

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

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 Существующие реализации алгоритма

C++: Chemical Descriptors Library (функция ullman).
C++: VF Library.

3 Литература

↑ Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.
↑ 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.

[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.

[1]

[2]

@@ Строка 7: / Строка 7: @@
 === Математическое описание алгоритма ===
+Пусть задан ориентированный граф <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>, удовлетворяющее условиям:
+.	<math>p(v, \varphi(v))</math> истинно для всех вершин <math>v \in V'</math>.
+.	Если вершины <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>.
+.	 <math>q(e,f)</math> истинно.
+Задача поиска изоморфных подграфов состоит в отыскании подграфов графа <math>G</math>, изоморфных графу-шаблону <math>H</math>.
 === Вычислительное ядро алгоритма ===
 === Макроструктура алгоритма ===