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

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

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

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

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