Isomorfismo de grafos

Carta Común · N.º 428012

En teoría de grafos, un isomorfismo de grafos es una biyección de los vértices de un grafo sobre otro, de modo que se preserva la adyacencia de los vértices. Más formalmente, el isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices f : V ( G ) → V ( H ) {\displaystyle f:V(G)\rightarrow V(H)} que preserva la relación de adyacencia.​ Es decir, cualquier par de vértices u y v de G son adyacentes si y solo si lo son sus imágenes, f(u) y f(v), en H. A pesar de su diferente aspecto, los dos grafos que se muestran a continuación son isomorfos: Dos grafos con matrices de adyacencia respectivas A y B serán isomorfos si y solo si existe una matriz permutación P tal que B = P A Pt.​

Leer en Wikipedia · Imagen CC BY-SA 3.0