Isomorfismo es un medio de decir si dos grafos son de la misma en algún sentido. Una buena manera de pensar de una isomorfo la "identidad" es como un "re-etiquetar" o una permutación de vértices. Esto es equivalente a la definición formal de un isomorfismo entre los gráficos:
Definición: Isomorfismo de grafos. Un isomorfismo entre la gráfica de $G_1(\boldsymbol {V_1},E)$ $G_2(\boldsymbol {V_2}, E')$ es un bijective (lo que significa que es a la vez uno-a-uno y en) la función$f$$V_1 \rightarrow V_2$, donde si $v_\alpha,v_\beta \in V_1$ son adyacentes, a continuación, $f(v_\alpha),f(v_\beta )\in V_2$ también son adyacentes.
Una vez que se puede pensar en esto como un re-etiquetado de los vértices conjunto, porque si dos vértices son adyacentes, entonces si se recalificado que no va a cambiar, y reetiquetado es, obviamente, bijective. He aquí un ejemplo sencillo:
![Wheel Graph]()
Si me muevo (mapa) cada vértice como he mostrado (con $F$ la asignación a sí mismo), entonces esto sería equivalente a la de simplemente moviendo las etiquetas de una manera similar. Sin embargo, no todos los gráficos tienen la simetría agradable de este, y así podemos hacer la pregunta más difícil: es isomorfo a:
![enter image description here]()
La simple respuesta aquí es buscar un explícito de isomorfismo (Sugerencia: $F \mapsto L$), pero una más iluminadora es mirar cómo podemos mover los vértices del segundo gráfico para parecerse a la primera, de modo que podríamos ver si de verdad son la misma gráfica sólo "recalificado". De hecho, nosotros simplemente mover un vértice y ver que son muy similares, y que un isomorfismo natural puede ser dibujada:
![enter image description here]()
Lo que sustenta este nociones de reetiquetado es poner más explícitamente en términos de matrices de adyacencia. Es decir, lo que estamos haciendo es decir: si queremos permutar la matriz de adyacencia de un grafo (es decir, nosotros re-orden de los vértices y sus copatrocinadoras columnas y filas) a ser el mismo que el de la matriz de adyacencia de otro gráfico, entonces son la misma gráfica.
