6 Isomorfismo e invariantes

Sean $G=(V,E)$ y $G^\prime=(V^\prime,E^\prime)$ dos grafos.

Si existe una bijección $\varphi:V\longrightarrow V^\prime$ entre los vértices de los grafos de tal manera que

$$xy\in E \Longleftrightarrow \varphi(x)\varphi(y)\in E^\prime$$

(es decir, si $x$ e $y$ son vecinos en $G$, lo son también $\varphi(x)$ y $\varphi(y)$ en $G^\prime$), entonces $G$ es isomorfo a $G^\prime$, $G\simeq G^\prime$ o también $G=G^\prime$, es decir, se dice el grafo $G$.

Una función $f$ sobre grafos con $f(G)=f(G^\prime)$ si $G\simeq G^\prime$ se llama invariante. Por ejemplo, invariantes son:

• $n$
• $m$
• ¿hay otras?

No se conoce ninguna invariante sobre grafos que se puede calcular en tiempo polinomial (y determinista) que decida que dos grafos son isomorfos, pero tampoco se ha comprobado hasta hoy que el problema de isomorfismo entre grafos sea $NP$-completo.

Recordamos que significa $NP$-completo:

Un problema pertence a la clase de problemas $NP$-completo, si existe una maquina de Turing no-determinista que resuelve el problema en tiempo polinomial respecto a la longitud de entrada y si todos los demás problemas dentro de la clase como mucho son más fáciles.

Entonces sabemos sobre problemas $NP$-completos:

• Existe un algoritmo para su solución.
• Si alguien nos da una solución podemos comprobar en tiempo polinomial que de verdad es una solución.
• Si conocemos un algoritmo polinomial para un problema $NP$-completo sabemos implícitamente algoritmos para todos los problemas de la clase cuyos tiempos de cálculo siguen siendo polinomial.
• Siempre se puede usar búsqueda exhaustiva para resolver el problema de forma determinista (con tiempo de ejecución exponencial).
• La pregunta de existencia de algoritmos polinomiales y deterministas para problemas $NP$-completos es una de las grandes preguntas abiertas en la informática.

Dado una bijección de los nodos entre dos grafos, es muy fácil comprobar si los dos grafos son isomorfos: basta con comparar las matrizes de adyacencia que se puede realizar en tiempo $O(m)$.