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

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] ложно в противном случае.

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

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

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

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

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