Isomorfismo de grafos

Isomorfismo de grafos
Los grafos simples G1 = (V1E1) y G2 = (V2E2) son isomorfos
si hay una funci ´on biyectiva f desde V1 a V2 con la propiedad
que a y b son adyacentes en G1 si y solo si f (a) y f (b) son
adyacentes en G2, para todo a y b en V1.
Tal funci ´on f es llamada un isomorfismo (igual forma).

Isomorfismo de grafos (2)
Ejercicio: Determinar si los grafos indicados sonisomorfos.
Figura: ejemplo isomorfismo de grafos

Isomorfismo de grafos
De Wikipedia, la enciclopedia libre
Saltar a navegación, búsqueda
En teoría de grafos, un isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices 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:
Grafo G | Grafo H | Un isomorfismo
entre G y H |
| | f(a) = 1 f(b) = 6f(c) = 8f(d) = 3f(g) = 5f(h) = 2f(i) = 4f(j) = 7 |
Dos grafos con matrices de adyacencia respectivas A y B serán isomofos si y solo si existe una matriz permutación P tal que B = P A P-1.[1]
[editar] Problema delisomorfismo de grafos
Artículo principal: Problema de isomorfismo de subgrafos
La determinación de si dos grafos con el mismo número de vértices n y aristas son isomorfos o no se conoce como el problema del isomorfismo de grafos. Este problema admite un ataque por fuerza bruta que exigiría comprobar si las n! biyecciones posibles preservan la adyacencia, pero no se conoce un algoritmo eficiente, almenos para el caso general. En este contexto, eficiencia debe interpretarse como crecimiento del número de pasos inferior a O(en).
El problema del isomorfismo de grafos presenta una curiosidad en teoría de complejidad computacional al ser uno de los pocos problemas citados por Garey y Johnson en 1979 pertenecientes a NP de los que se desconoce si es resoluble en tiempo polinómico o si esNP-completo (actualmente está en revisión la demostración de que el problema está en P). [

Teorema de Lagrange (teoría de grupos)
De Wikipedia, la enciclopedia libre
Saltar a navegación, búsqueda
En la teoría de grupos, el teorema de Lagrange es un resultado importante que relaciona el orden de un grupo finito G con el orden de cualquiera de sus subgrupos. Más precisamente, afirma que si G es ungrupo finito y H es un subgrupo de G, entonces
(1)
donde | G | y | H | son el orden del grupo G y el orden del subgrupo H, en tanto que [G:H] es el índice de H en G.

El recíproco del teorema de Lagrange es falso, pues existen grupos de orden m que pueden no tener un subgrupo de orden n a pesar de que . Por ejemplo, el grupo simétrico S4 tiene orden 24 y no tiene ningún subgrupo de orden 6. Engeneral, los grupos no resolubles son ejemplos en los que el recíproco del teorema de Lagrange no aplica.
Por otra parte, el recíproco del teorema de Lagrange es siempre cierto para el caso de grupos abelianos, y por tanto lo es también para grupos cíclicos.

[editar] Consecuencias
Una consecuencia inmediata del teorema de Lagrange es que todo grupo G de orden primo p es cíclico, pues el ordende un elemento a de G debe dividir p, y si dicho elemento es distinto de la identidad de G, entonces resulta que el orden de a sólo puede ser p, de modo que a es un generador de G.

A partir del teorema de Lagrange puede, por ejemplo, demostrarse que si H,K son subgrupos finitos de un grupo G, entonces
(2) ,
donde (este conjunto puede no ser un subgrupo de G).

El teorema de Lagrangeproporciona una forma interesante de demostrar que el orden del grupo simétrico Sn de las permutaciones de n símbolos es n! (cf. Serge 2002, p. 13). Además, si An es el subgrupo alternante de Sn, entonces

pues .
[editar] Generalización
El teorema de Lagrange es en realidad un caso especial del hecho siguiente:
Si H y K son dos subgrupos de un grupo G, siendo K a su vez un subgrupo de H, entonces...