Уровень задачи

Поиск изоморфных подграфов

Материал из Алговики
Перейти к навигации Перейти к поиску


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

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

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

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

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

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

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

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

4 Литература

  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.