Problem izomorfizmu podgrafów
Z Wikipedii
W teorii złożoności obliczeniowej, problem izomorfizmu podgrafów jest przykładem NP-zupełnego problemu decyzyjnego. Formalna definicja tego problemu wygląda następująco:
- Dla podanych grafów G i F określić czy istnieje podgraf G izomorficzny z F.
Problem ten występuje w chemii informatycznej przy wyszukiwaniu związków chemicznych zawierających określone podstruktury. Do wyszukiwania takich podstruktur używane są zapytania w formacie SMARTS (stanowiącym rozszerzenie formatu SMILES).
Uogólnieniem tego problemu jest optymalizacyjny NP-zupełny problem maksymalnego wspólnego podgrafu, polegający na znalezieniu izomorficznych do siebie podgrafów G i F o maksymalnej wielkości
[edytuj] Zobacz też
[edytuj] Literatura
- Jeffrey D. Ullman: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
