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

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

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

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

• для фиксированного графа [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.4 Макроструктура алгоритма

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

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

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

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

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

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

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