Problem izomorfizmu podgrafu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

W teorii złożoności obliczeniowej, problem izomorfizmu podgrafu 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

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.