ІЗОМОРФІЗМ ГРАФІВ( GRAPH ISOMORPHISM )

Реалізація алгоритмів розв'язання задач із ізоморфності графів

GRAPH ISOMORPHISM PROBLEM ( finding exact isomorphisms, simple graph isomorphism algorithm of Read & Corneil [1,3] )

SUBGRAPH ISOMORPHISM PROBLEM ( Ullman's algorithm [2,4] )

MAXIMUM COMMON SUBGRAPH PROBLEM (Ullman's algorithm [2,4] )

Виконав: Андрєєв М.С. (02-ВВ2)

Керівник: Дубінін В.М.

1.ВИЗНАЧЕННЯ ІЗОМОРФІЗМУ ГРАФІВ

GRAPH ISOMORPHISM PROBLEM ( finding exact isomorphisms, simple graph isomorphism algorithm of Read & Corneil [1,3] )

Визначення ізоморфності ведеться за спрощеною схемою алгоритму Ульмана (див. наступний пункт).

Розглянемо приклад роботи програми:

Перший граф: Другий граф:

SHAPE \* MERGEFORMAT

graph

Спочатку задаються розміри матриць суміжності графів, потім у поля, що розкрилися, вводяться вихідні дані, які можна зберегти у файл або завантажити з файлу. По головній діагоналі матриць розставляються ваги вершин, дуги можуть мати ваги. Матриця відповідності вершин показує відповідність вершин 2-го графа (рядка) вершин 1-го графа (стовпці).

графів

2. ПОШУК ІЗОМОРФНОГО ПІДГРАФУ

SUBGRAPH ISOMORPHISM PROBLEM ( Ullman's algorithm [2,4] )

Оригінальний псевдокод алгоритму:

графів

На основі даного алгоритму було розроблено адаптований алгоритм, який дозволяє визначати ізоморфізм графів та/або ізоморфний підграф в іншому графі, у тому числі і у випадках, коли ваги всіх вершин рівні.

Ullman базується на algoritm для finding exact isomorfphisms the common subgraph G1 to G

1. Let Pij be an permutation matrix, n = V, M і M1

denote the adjacency matrices of G and G1, respectively.

3.procedureBacktrackMOD1(adjacency matrix M,adjacency matrix M1,permutation matrix P, counter k)

(a) if k>n then P represents a subgraph isomorphism from G1 to G.

Output P and return.

for all i = 1 to n

(d) for all i = 1 to n

I. Set P(k,i) = 1 і для всіх j not equal i set P(i,j) = 0

V.if (MM = M111 і M12(k,k)=M1(i,i) ) Call BacktrackMOD1(M,M1,P,k+1)

VI. if (MM не еквівалент M111 і i = n) для всіх j = 1 до n P(k,j)=0

Розглянемо приклад роботи програми:

Перший граф: Другий граф:

SHAPE \* MERGEFORMAT

ізоморфізм

Спочатку задаються розміри матриць суміжності графів, потім у поля, що розкрилися, вводяться вихідні дані, які можна зберегти у файл або завантажити з файлу. По головній діагоналі матриць розставляються ваги вершин, дуги можуть мати ваги. Матриця відповідності вершин показує відповідність вершин 2-го графа (рядка) вершин 1-го графа (стовпці).

графів

3. ПОШУК МАКСИМАЛЬНОГО ЗАГАЛЬНОГО ПІДГРАФУ

MAXIMUM COMMON SUBGRAPH PROBLEM (Backtracking search, McGregor's algorithm[1,5])

На основі алгоритму Ульмана було розроблено алгоритм пошуку загального ізоморфного графа.

llman Базований algorithm для перегляду загального повідомлення

1. Let Pij be an permutation matrix, n = V, M і M1

denote the adjacency matrices of G and G1, respectively.

3.procedure BacktrackMOD(adjacency matrix M,adjacency matrix M1,permutation matrix P, counter k)

(a) if k>n then P represents a subgraph isomorphism from G and G1.

Output P and return.

(b) for all i = 1 to n

I. Set Pki = 1 і для всіх j not equal і set Pij = 0

V.if MM = M12 call BacktrackMOD(M,M1,P,k+1)

VI. if MM не еквівалент S12 для всіх j =1 to n Pkj=0

Розглянемо приклад роботи програми:

Перший граф: Другий граф:

SHAPE \* MERGEFORMAT

ізоморфізм

Спочатку задаються розміри матриць суміжності графів, потім у поля, що розкрилися, вводяться вихідні дані, які можна зберегти у файл або завантажити з файлу. По головній діагоналі матриць розставляються ваги вершин, дуги можуть мати ваги. Після введення даних необхідно збільшити розмірність матриць на одиницю і натиснути кнопку Go . Матриця відповідності вершин показує відповідність вершин 2-го графа (рядка) вершин 1-го графа (стовпці).

графів

4. DOWNLOAD

  1. Програма, що реалізує простий алгоритм визначення ізоморфності двох графів, exe-файл (ZIP-архів, 15 K)
  2. Програма, що реалізує алгоритм Ульмана (*) (визначення ізоморфізму графів та підграфів, а також визначення максимального загального підграфа), Visual C++ 6.0 проект, exe- та dll-файли (ZIP, 937 K)
  3. Програма, що реалізує алгоритм пошуку з поверненнями МакГрегора (**) для визначення максимального загального підграфа, Visual C++ 6.0 проект, exe- та dll-файли (ZIP, 947 K)

(*) У методі Ульмана при знаходженні загального підграфа до матриць треба додавати по порожньому рядку. При пошуку ізоморфного підграф це робити не треба.

(**) Backtracking search , McGregor ' s algorithm [1,5]). Це алгоритм пошуку у графі із поверненнями. У цьому роботі не розглянуто. Програма видає відповідність вершин другого графа вершин знайденого підграфа.

Основний рез-т - це знайдений підграф. Недолік – немає відповідності вершин знайденого загального підграфу вершин вихідних графів.

5. ЛІТЕРАТУРА

1. Rebecca Moore, “Beyond parsing RDF: Val >2003