[quote="cristianmvv";p=347949]
Personalmente opino que es feo mantenerlo vivo asi, hasta que se caigan los servidores y no con un final digno... pero la verdad es que es jodido darle un final digno ya. Bue, tu veras que eres el que tiene el dedo terminador[/quote]
Los servidores están bajo mantenimiento obligatorio y no te preocupes, cada 2 x 3 están haciendo backups para asegurar que la información no se eche a perder cumpliendo todos los estándares de seguridad.
[quote="geballo";p=347950]
Me lo puedes clarificar por favor?
El problema de isomorfismo tiene cono entrada 2 grafos mientras que clique tiene como entrada 1 grafo y un entero k. Como tengo que modificar el input te el primero para pasarlo por el segundo?
No debo también demostrar que puedo validar el certificado de isomorfismo en tiempo polinomico?[/quote]
Se puede demostrar mediante la reducción de este problema al Problema de la clique, como ya he posteado antes, que lo he consultado y me indica lo siguiente:- 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.
En este caso si es NP-Completo, la jerarquía polinomial colapsa. Prefiero que lo consultes porque la verdad no puedo especificar exactamente, no tengo la suficiente teoría que yo recuerde, llegué a este tipo de tema y no tengo la suficiente información para poder ayudarte, lo siento, mejor que vayas a Wikipedia u otros portales que al igual encontrarás datos adicionales.










