Алгоритм Ульмана
Зміст
1 Властивості та структура алгоритму
1.1 Загальний опис алгоритму
Алгоритм Ульмана[1] [2] вирішує завдання пошуку ізоморфних підграф за експоненційний час, при цьому
- для фіксованого графа [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.3 Обчислювальне ядро алгоритму
1.4 Макроструктура алгоритму
Визначимо булеву матрицю [math]B= ( B_ )[/math] розміру так:
• [math]B_[/math] істинно, якщоне виключена можливість, що [math]\varphi(v_i )=w_j[/math] ;
• [math]B_[/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] .
1.7 Інформаційний граф
1.8 Ресурс паралелізму алгоритму
Перебір може бути ефективно паралелізований [3] , зокрема з використанням графічних прискорювачів [4] . Відомі реалізації, що працюють безпосередньо з графовими базами даних[5] [6].
1.9 Вхідні та вихідні дані алгоритму
1.10 Властивості алгоритму
2 Програмна реалізація алгоритму
2.1 Особливості реалізації послідовного алгоритму
2.2 Локальність даних та обчислень
2.2.1 Локальність реалізації алгоритму
2.2.1.1 Структура звернень на згадку та якісна оцінка локальності
2.2.1.2 Кількісна оцінка локальності
2.3 Можливі способи та особливості паралельної реалізації алгоритму
Програма, що реалізує пошук транзитного замикання, складається з CPU частини, що відповідає за загальну координацію обчислень, що використовує допоміжні класи.