Problem izomorfizmu podgrafu
W tym artykule dokładnie zbadamy zjawisko Problem izomorfizmu podgrafu i jego implikacje w dzisiejszym społeczeństwie. Od jego powstania po możliwe przyszłe konsekwencje, szczegółowo przeanalizujemy każdy aspekt związany z Problem izomorfizmu podgrafu, aby zapewnić kompleksową i kompletną wizję tego tematu. Zbierając dane, przeglądając badania i konsultując się z ekspertami, staramy się rzucić światło na Problem izomorfizmu podgrafu i zaoferować naszym czytelnikom świadomą i wzbogacającą perspektywę. Czytaj dalej, aby odkryć wszystko, co musisz wiedzieć o Problem izomorfizmu podgrafu i jego znaczeniu we współczesnym świecie.
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ż
Literatura
- Jeffrey D. Ullman: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
| Najważniejsze pojęcia | |
|---|---|
| Wybrane klasy grafów | |
| Algorytmy grafowe | |
| problemy grafowe | |
| Inne zagadnienia |
