PUNTOS EXTRA

ISOMORFISMO


Dos grafos son isomorfos cuando tienen la misma estrucura, es decir sus vértices están relacionados de igual forma aunque esten dibujados de manera distinta.

Condiciones necesarias para que dos grafos sean isomorfos:

-Deben tener la misma cantidad de vertices.

-Deben tener la misma cantidad de aristas.

-Deben tener los mismos grados de los vértices.

-Deben tener caminos de las mismas longitudes.

-Si uno tiene ciclos, el otro también debe tenerlos.


Analizaremos si los siguientes grafos son isomorfos:
(Para hacer más grande la imagen hacer click sobre ella)













Vemos que ambos tienen 4 vértices y 5 aristas.

Ahora vamos a definir la función biyectiva, haciendo corresponder los vértices con iguales grados:

f(A)=Y;

f(B)=Z;

f(C)=X;

f(D)=W;

Ahora la definición dice que si entre 2 vértices del primer grafo hay una arista,también debe haber arista entre los vértices del segundo grafo.

Por ejemplo vemos en la imagen anterior que en el G1(grafo 1) entre A y B hay una arista, y también hay una arista entre f(A) y f(B) en el G2(grafo 2).

Esto mismo habría que revisar para cada arista, ordenando convenientemente los vértices.

En la siguiente tabla se observa la cantidad de aristas que unen a cada par de vértices:
(Para ver más grande la imagne hacer click sobre ella)












Por ejemplo nosotros pusimos como función biyectiva f(A)=Y y f(B)=Z, y vemos que del vértice A al vértice B hay una arista, esto en el grafo 1; en el grafo 2 vemos que concuerda con su biyectiva porque del vértice Y al vértice Z también hay una arista.

Como las tablas con sus respectivos valores tienen las mismas cantidades de aristas, podemos asegurar que G1 es isomorfo a G2.