Поиск изоморфных подграфов: различия между версиями

[непроверенная версия]

[досмотренная версия]

Текущая версия от 14:03, 6 марта 2018

Постановка задачи

Пусть заданы два графа [math]\displaystyle{ G }[/math] и [math]\displaystyle{ H }[/math]. Задача поиска изоморфных подграфов состоит в том, чтобы определить, существует ли у графа [math]\displaystyle{ G }[/math] подграф, изоморфный [math]\displaystyle{ H }[/math], и в случае положительного ответа – предъявить хотя бы один такой подграф.

Свойства задачи

Задача поиска изоморфных подграфов является NP-полной, поэтому не существует известных алгоритмов, решающих её за полиномиальное время.

Алгоритмы решения задачи

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

для фиксированного графа [math]\displaystyle{ H }[/math] время полиномиальное;
для планарного графа [math]\displaystyle{ G }[/math] время работы линейное (при фиксированном графе [math]\displaystyle{ H }[/math]).

Алгоритм VF2^[3] разработан специально для применения на больших графах.

Литература

↑ Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.
↑ Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.
↑ Cordella, L P, P Foggia, C Sansone, and M Vento. “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.” IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 10 (October 2004): 1367–72. doi:10.1109/TPAMI.2004.75.

[1] Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.

[2] Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.

[3] Cordella, L P, P Foggia, C Sansone, and M Vento. “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.” IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 10 (October 2004): 1367–72. doi:10.1109/TPAMI.2004.75.

[1]

[2]

[3]

@@ Строка 1: / Строка 1: @@
-== Свойства и структура алгоритмов ==
+{{level-p}}
-=== Общее описание алгоритма ===
-Пусть заданы два графа <math>G</math> и <math>H</math>. '''Задача поиска изоморфных подграфов''' состоит в том, чтобы определить, существует ли у графа <math>G</math> подграф, изоморфных <math>H</math>, и в случае положительного ответа – предъявить хотя бы один такой подграф.
+== Постановка задачи ==
+Пусть заданы два графа <math>G</math> и <math>H</math>. '''Задача поиска изоморфных подграфов''' состоит в том, чтобы определить, существует ли у графа <math>G</math> подграф, изоморфный <math>H</math>, и в случае положительного ответа – предъявить хотя бы один такой подграф.
+== Свойства задачи ==
 Задача поиска изоморфных подграфов является NP-полной, поэтому не существует известных алгоритмов, решающих её за полиномиальное время.
-'''Алгоритм Ульмана'''<ref>Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.</ref><ref>Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.</ref> решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом
+== Алгоритмы решения задачи ==
+'''[[Алгоритм Ульмана]]'''<ref>Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.</ref><ref>Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.</ref> решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом
 * для фиксированного графа <math>H</math> время полиномиальное;
 * для планарного графа <math>G</math> время работы линейное (при фиксированном графе <math>H</math>).
-=== Математическое описание ===
+'''[[Алгоритм VF2]]'''<ref>Cordella, L P, P Foggia, C Sansone, and M Vento. “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.” IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 10 (October 2004): 1367–72. doi:10.1109/TPAMI.2004.75.</ref> разработан специально для применения на больших графах.
-=== Вычислительное ядро алгоритма ===
-=== Макроструктура алгоритма ===
-=== Описание схемы реализации последовательного алгоритма ===
-=== Последовательная сложность алгоритма ===
-=== Информационный граф ===
-=== Описание ресурса параллелизма алгоритма ===
-=== Описание входных и выходных данных ===
-=== Свойства алгоритма===
-== Программная реализация алгоритмов ==
-=== Особенности реализации последовательного алгоритма ===
-=== Описание локальности данных и вычислений ===
-=== Возможные способы и особенности реализации параллельного алгоритма ===
-=== Масштабируемость алгоритма и его реализации ===
-=== Динамические характеристики и эффективность реализации алгоритма ===
-=== Выводы для классов архитектур ===
-=== Существующие реализации алгоритма ===
 == Литература ==
 <references />
+[[Категория:Статьи в работе]]