Problema d'isomorfisme de subgrafos
En complexitat computacional, el Problema d'isomorfisme de subgrafos, també a voltes cridat Problema de matching de subgrafos, és un problema de decisió NP-complet, que formalment, es definix de la següent manera:
La NP-completitud del problema es demostra per mig de la reducció d'este problema al Problema de la clique. Si el Problema d'isomorfisme de subgrafos anara polinomial, podria utilisar-se per a resoldre el Problema de la clique, també en temps polinomial. Siga n el número d'arestes de G, es pot eixecutar el problema d'isomorfisme de subgrafos n-2 voltes (sent G1 una clique de tamany 3 a n, i G2 sent G) per a trobar el clique més gran en G.
Este problema és una generalisació del possiblement més senzill Problema d'isomorfisme de grafos, en el sentit que si este últim és NP-complet, llavors la jerarquia polinòmica colapsa, aixina que se supon que no deuria ser aixina.
Vore també
Referències
- J. R. Ullmann: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
- Michael R. Garey i David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman. ISBN 0-7167-1045-5. A1.4: GT48, pg.202.
- Este artícul conté una traducció derivada de «Problema de isomorfismo de subgrafos» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.