Problem izomorfizmu podgrafu

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ż

• izomorfizm grafów
• homeomorfizm grafów

Literatura

• Jeffrey D. Ullman: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.