Алгоритм Ульмана

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

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

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

• для фиксированного графа $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$.

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

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

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