Teoría de grafos

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos.

Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas.

Se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Isomorfismo

Un isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices.

La función es biyectiva si es al mismo tiempo inyectiva y sobreyectiva; es decir, si todos los elementos del conjunto de salida tienen una imagen distinta en el conjunto de llegada.

y a cada elemento del conjunto de llegada le corresponde un elemento del conjunto de salida.

 Una función es inyectiva si a cada valor del conjunto X le corresponde un valor distinto en el conjunto Y de f.

Es decir, a cada elemento del conjunto X le corresponde un solo valor de Y tal que, en el conjunto X no puede haber dos o más elementos que tengan la misma imagen.

 

  f: V(G) =  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.

Una función es sobreyectiva cuando la imagen, elemento de "Y" es la imagen de como mínimo un elemento de "X".