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 grafosG y H es una biyección f entre los conjuntos de sus vértices que preserva la relación de adyacencia.[1] 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:
La determinación de si dos grafos con el mismo número de vértices n y aristas m 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(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 es NP-completo (actualmente está en revisión la demostración de que el problema está en P).[3]
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, ISBN978-0716710455, OCLC 11745039.
Bibliografía
Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN978-84-7476-631-8. OCLC 871814053.
Datos:Q303100
Multimedia:Category:Graph isomorphism
Enero 09, 2022
isomorfismo, grafos, teoría, grafos, isomorfismo, grafos, biyección, vértices, grafo, sobre, otro, modo, preserva, adyacencia, vértices, más, formalmente, isomorfismo, entre, grafos, biyección, entre, conjuntos, vértices, displaystyle, rightarrow, preserva, re. En teoria de grafos un isomorfismo de grafos es una biyeccion de los vertices de un grafo sobre otro de modo que se preserva la adyacencia de los vertices Mas formalmente el isomorfismo entre dos grafos G y H es una biyeccion f entre los conjuntos de sus vertices f V G V H displaystyle f V G rightarrow V H que preserva la relacion de adyacencia 1 Es decir cualquier par de vertices u y v de G son adyacentes si y solo si lo son sus imagenes f u y f v en H A pesar de su diferente aspecto los dos grafos que se muestran a continuacion son isomorfos Grafo G Grafo H Un isomorfismo entre G y Hf a 1 displaystyle f a 1 f b 6 displaystyle f b 6 f c 8 displaystyle f c 8 f d 3 displaystyle f d 3 f g 5 displaystyle f g 5 f h 2 displaystyle f h 2 f i 4 displaystyle f i 4 f j 7 displaystyle f j 7 Dos grafos con matrices de adyacencia respectivas A y B seran isomorfos si y solo si existe una matriz permutacion P tal que B P A Pt 2 Indice 1 Problema del isomorfismo de grafos 2 Aplicaciones 3 Vease tambien 4 Referencias 5 BibliografiaProblema del isomorfismo de grafos EditarArticulo principal Problema de isomorfismo de subgrafos La determinacion de si dos grafos con el mismo numero de vertices n y aristas m son isomorfos o no se conoce como el problema del isomorfismo de grafos Este problema admite un ataque por fuerza bruta que exigiria 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 numero de pasos inferior a O en El problema del isomorfismo de grafos presenta una curiosidad en teoria 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 polinomico o si es NP completo actualmente esta en revision la demostracion de que el problema esta en P 3 Aplicaciones EditarEn analisis de redes sociales los estudios de diadas y triadas en redes sociales se basan en isomorfismos de subgrafos muy pequenos 1 Vease tambien EditarHomomorfismo de grafosReferencias Editar a b Wasserman y Faust 2013 Grafos y matrices por Dawn Iacobucci pp 121 188 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 Bibliografia EditarWasserman Stanley Faust Katherine 2013 1994 Analisis de redes sociales Metodos y aplicaciones Madrid Centro de Investigaciones Sociologicas ISBN 978 84 7476 631 8 OCLC 871814053 Datos Q303100 Multimedia Category Graph isomorphism Obtenido de https es wikipedia org w index php title Isomorfismo de grafos amp oldid 135090870, wikipedia, wiki, leyendo, leer, libro, biblioteca,
