Una Introducción Gentíl a la Teoría de Grafos: Parte 2
Isomorfismos
Antes de comenzar a leer este artículo, si no leíste el primero de esta serie, puedes encontrarlo en el siguiente enlace.
En teoría de grafos, como en otras áreas de las matemáticas, existe el concepto de isomorfismo, que significa “igualdad de forma”. La distinción entre igual e isomorfo se da porque, si recordamos en la parte 1, se dijo que los grafos se definen por dos conjuntos, uno de vértices (vertices) que contiene los nombres de los puntos y uno de aristas (edges) que contiene subconjuntos con pares del conjunto de vértices. Entonces, dos grafos son iguales si los elementos (nombres de los puntos) del conjunto de vértices es igual y si los pares del conjunto de aristas son iguales; en otras palabras, los dos conjuntos que forman el grafo 1 son iguales a los dos conjuntos que forman el grafo 2.
Por otro lado, si los grafos tienen la misma estructura, pero con elementos diferentes, a los grafos se les llama isomorfos (tal vez sea mas claro con un ejemplo).
Def: Se dice que dos grafos son isomorfos si existe una correspondencia uno a uno entre sus conjuntos de vértices tal que, cuando dos vértices sean adyacentes en un grafo, los vértices correspondientes en el otro grafo también son adyacentes.
Ejemplo
Determinemos si C⁵ y su complemento son isomorfos. Tratemos de “acomodar” las etiquetas de los vértices de C⁵ en el otro grafo.
- A la etiqueta (1) de C⁵ complemento la llamaremos (A)
2. En C⁵ el vértice (A) está conectado con los vértices (B) y (E), por tanto, a los vértices (3) y (4) los voy a llamar (B) y (E).
3. El vértice (B) está conectado con (A) y (C ), ya tenemos la conexión con (A), entonces el vértice (5) lo llamaremos (C ). Lo mismo para el vértice (E) que está conectado con (D), por tanto el vértice (2) lo llamaremos (D).
4. Hasta el momento sabemos que A, B y E están igual en ambos grafos, y sabemos que al menos una de las conexiones de D y C es correcta. La conexión final es C con D y podemos ver que en efecto también existe en C⁵ complemento.
5. Por todo lo anterior, deducimos que el grafo C⁵ es isomorfo a su complemento.
La técnica anterior suele llamarse “reemplazo de etiquetas”. Como podrán imaginar hacer esto para grafos muy grandes se vuelve muy engorroso y se presta para muchos errores. Los siguientes criterios son necesarios pero no suficientes para determinar si dos grafos son isomorfos.
- Tienen igual número de vértices
- Tienen igual número de aristas (edges)
- Los grados de los vértices están igualmente distribuidos: El grado de un vértice es el número de conexiones (aristas/edges) que tiene. En el caso de C⁵ y su complemento, todos los vértices tienen grado 2.
- El número de piezas de los grafos: Imaginemos un grafo que son dos cubos separados, es decir, ningún vértice del cubo 1 se conecta con otro vértice del cubo 2. Este grafo tiene 2 piezas.
En matemáticas todo se debe decir, incluso lo obvio. Se dice que dos grafos son diferentes si no son isomorfos.
Hallar isomorfismos es sencillo hasta que no lo es. Para grafos muy pequeños se pueden hacer diferentes pruebas para determinar si son isomorfos; pero, conforme crecen los grafos la dificultad aumenta incluso para las computadoras. Algunos algoritmos como Nauty solucionan este problema usando algunas propiedades mas avanzadas como son los automorfismos. Este problema en particular se considera como NP en teoría de complejidad computacional.
