La NP-completitud del problema se demuestra mediante la reducción de este problema al Problema de la clique. Si el Problema de isomorfismo de subgrafos fuese polinomial, podría utilizarse para resolver el Problema de la clique, también en tiempo polinomial. Sea n el número de aristas de G, se puede ejecutar el problema de isomorfismo de subgrafos n-2 veces (siendo G1 una clique de tamaño 3 a n, y G2 siendo G) para encontrar el clique más grande en G.
Este problema es una generalización del posiblemente más sencillo Problema de isomorfismo de grafos, en el sentido que si este último es NP-completo, entonces la jerarquía polinómica colapsa, así que se supone que no debería ser así.
problema, isomorfismo, subgrafos, complejidad, computacional, también, veces, llamado, problema, matching, subgrafos, problema, decisión, completo, formalmente, define, siguiente, manera, isomorfismo, subgrafos, entrada, grafos, pregunta, isomorfo, subgrafo, c. En complejidad computacional el Problema de isomorfismo de subgrafos tambien a veces llamado Problema de matching de subgrafos es un problema de decision NP completo que formalmente se define de la siguiente manera Isomorfismo de subgrafos G1 G2 Entrada Dos grafos G1 y G2 Pregunta Es G1 isomorfo a un subgrafo de G2 La NP completitud del problema se demuestra mediante la reduccion de este problema al Problema de la clique Si el Problema de isomorfismo de subgrafos fuese polinomial podria utilizarse para resolver el Problema de la clique tambien en tiempo polinomial Sea n el numero de aristas de G se puede ejecutar el problema de isomorfismo de subgrafos n 2 veces siendo G1 una clique de tamano 3 a n y G2 siendo G para encontrar el clique mas grande en G Este problema es una generalizacion del posiblemente mas sencillo Problema de isomorfismo de grafos en el sentido que si este ultimo es NP completo entonces la jerarquia polinomica colapsa asi que se supone que no deberia ser asi Vease tambien EditarIsomorfismo de grafosReferencias EditarJ R Ullmann An Algorithm for Subgraph Isomorphism Journal of the ACM 23 1 31 42 1976 Michael R Garey y 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 Datos Q2528185 Obtenido de https es wikipedia org w index php title Problema de isomorfismo de subgrafos amp oldid 119831927, wikipedia, wiki, leyendo, leer, libro, biblioteca,
