Поиск изоморфных подграфов: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) (Общее описание алгоритма) |
Daryin (обсуждение | вклад) (Алгоритм Ульмана вынесен в отдельную статью, добавлен VF2) |
||
| Строка 1: | Строка 1: | ||
| − | == | + | == Постановка задачи == |
| − | |||
Пусть заданы два графа <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-полной, поэтому не существует известных алгоритмов, решающих её за полиномиальное время. | Задача поиска изоморфных подграфов является 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>H</math> время полиномиальное; | ||
* для планарного графа <math>G</math> время работы линейное (при фиксированном графе <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 /> | <references /> | ||
Версия 18:51, 18 июня 2015
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 Литература
- ↑ 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.
