Diferencia entre revisiones de «Isomorfismo de grafos»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 01:20 23 oct 2010

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 $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:

Grafo G	Grafo H	Un isomorfismo entre G y H
		$f(a)=1$ $f(b)=6$ $f(c)=8$ $f(d)=3$ $f(g)=5$ $f(h)=2$ $f(i)=4$ $f(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]

Problema del isomorfismo 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, al menos para el caso general. En este contexto, eficiencia debe interpretarse como crecimiento del número de pasos inferior a O(eⁿ).

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 es NP-completo (actualmente está en revisión la demostración de que el problema está en P). ^[2]

Referencias

↑ Jonathan L. Gross, Jay Yellen.Handbook of Graph Theory. CRC Press, 2004. ISBN 158488090
↑ *Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 978-0716710455, OCLC 11745039 .

[1] Jonathan L. Gross, Jay Yellen.Handbook of Graph Theory. CRC Press, 2004. ISBN 158488090

[2] *Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 978-0716710455, OCLC 11745039 .

[1]

[2]

Revisión del 01:18 23 oct 2010 editar 186.26.154.24 (discusión) Sin resumen de edición ← Ir a diferencia anterior		Revisión del 01:20 23 oct 2010 editar deshacer Wikiedro (discusión · contribs.) Autoverificados, Reversores 54 090 ediciones m Deshecha la edición de 186.26.154.24: vandalismo en ortografía Ir a siguiente diferencia →
Línea 1:		Línea 1:
	En [[teoría de ~~gafos~~]], un '''[[isomorfismo]]''' entre dos [[~~gafo~~]]s ''G'' y ''H'' es una [[biyección]] ''f'' entre los conjuntos de sus [[vértice (teoría de ~~gafos~~)\|vértices]] <math> f: V(G) \rightarrow V(H) </math> 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''.		En [[teoría de grafos]], un '''[[isomorfismo]]''' entre dos [[grafo]]s ''G'' y ''H'' es una [[biyección]] ''f'' entre los conjuntos de sus [[vértice (teoría de grafos)\|vértices]] <math> f: V(G) \rightarrow V(H) </math> 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:		A pesar de su diferente aspecto, los dos grafos que se muestran a continuación son isomorfos: