Алгоритм Ульмана: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
ASA (обсуждение | вклад) Нет описания правки |
Teplov (обсуждение | вклад) |
||
| Строка 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>, удовлетворяющее условиям: | |||
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>. | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
Версия от 16:35, 18 ноября 2016
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм Ульмана[1][2] решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом
- для фиксированного графа [math]\displaystyle{ H }[/math] время полиномиальное;
- для планарного графа [math]\displaystyle{ G }[/math] время работы линейное (при фиксированном графе [math]\displaystyle{ H }[/math]).
Математическое описание алгоритма
Пусть задан ориентированный граф [math]\displaystyle{ G=(V,E) }[/math] с вершинами [math]\displaystyle{ V= ( v_1,v_2,...,v_n) }[/math] и рёбрами [math]\displaystyle{ E=(e_1,e_2,...,e_m) }[/math] , и ориентированный граф [math]\displaystyle{ H=(W,F) }[/math] с вершинами [math]\displaystyle{ W=(w_1,w_2,...,w_n) }[/math] и рёбрами [math]\displaystyle{ F=(f_1,f_2,...,f_m) }[/math]. Булевы функции [math]\displaystyle{ p(v_i,w_j ) }[/math] и [math]\displaystyle{ q(e_i,f_j ) }[/math] задают совместимость вершин и рёбер двух графов (например, что вершины помечены одним и тем же химическим элементом).
Подграф [math]\displaystyle{ G'=(V',E' ) }[/math] графа [math]\displaystyle{ G }[/math] изоморфен графу [math]\displaystyle{ H }[/math], если существует взаимно-однозначное отображение [math]\displaystyle{ \varphi:V' \rightarrow W }[/math], удовлетворяющее условиям:
1. [math]\displaystyle{ p(v, \varphi(v)) }[/math] истинно для всех вершин [math]\displaystyle{ v \in V' }[/math].
2. Если вершины [math]\displaystyle{ v_1,v_2 \in V' }[/math] и [math]\displaystyle{ e=(v_1,v_2 ) \in E }[/math], то [math]\displaystyle{ e \in E' }[/math] и существует соответствующее ребро [math]\displaystyle{ f=( \varphi (v_1 ), \varphi (v_2 )) \in F }[/math].
3. [math]\displaystyle{ q(e,f) }[/math] истинно.
Задача поиска изоморфных подграфов состоит в отыскании подграфов графа [math]\displaystyle{ G }[/math], изоморфных графу-шаблону [math]\displaystyle{ H }[/math].
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- C++: Chemical Descriptors Library (функция
ullman). - C++: VF Library.
Литература
- ↑ 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.