Problem izomorfizmu podgrafu
Wygląd
Problem izomorfizmu podgrafu – przykład 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
Zobacz też[edytuj | edytuj kod]
Literatura[edytuj | edytuj kod]
- Jeffrey D. Ullman: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.