• Registro
Foro de preguntas y respuestas de matemáticas, de cualquier nivel. Cuánto más interesantes, divertidas o intrépidas, mejor.
Aviso: Te invitamos a conocer la página de Facebook de la UCIM

Ganas puntos al hacer preguntas, contestarlas y, sobre todo, si tu respuesta es seleccionada como la mejor.
Registrate como usuario para participar en el foro. También puedes utilizar tu identidad de FB Utiliza el botón azul para ingresar (si usas tu identidad de FB y estás logeado en FB, automáticamente te reconoce).

El irracional tiene una página en FB. El Irracional






Homomorfismos en gráficas, libro

+1 voto
¿Me pueden recomendar un libro donde se hable sobre homomorfismos en gráficas, se den ejemplos, y si es posible, se hable un poco del aspecto algoritmico? Por ejemplo, que el problema es NP-completo, o si existen familias de gráficas para las que no lo es, etc.

O algún artículo muy básico que hable sobre homomorfismos.
preguntado por dlara (1,780 puntos) Nov 19, 2013 en Libros y artículos

2 Respuestas

+1 voto

No conozco ningún libro que tenga el aspecto algorítmico de homorfismos de gráficas. Acerca de homomorfismos (y en particular isomorfismos y automorfismos) de gráficas puedes encontrar mucha teoría y ejemplos en

Chris Godsil, Gordon Royle, Algebraic graph theory, Graduate Texts in Mathematics, 207. Springer-Verlag, New York, 2001.

Por cierto, ¿a qué problema NP-completo te refieres?

respondido por Daniel Pellicer (2,220 puntos) Nov 19, 2013
Me refiero al problema de decidir, dadas dos gráficas, si existe un homomorfismo entre estas. También, me interesa saber si existen familias de gráficas para las que este problema sea polinomial.

Mirare el libro, gracias Daniel.
+2 votos


Encontre dos articulos introductorios pero bastantes completos, uno de los cuales cubre precisamente la parte computacional que estaba buscando. Dejo las referencias por si le fueran utiles a alguien.

Graph homomorphisms: structure and symmetry.
G Hahn, C Tardif- Graph Symmetry, 1997, Springer.

http://www.mast.queensu.ca/~ctardif/articles/ghss.pdf


Gena Hahn and Gary MacGillivray. "Graph homomorphisms: computational aspects and infinite graphs". Research report, UniversitÈ de Montreal, June 2002.
http://www.ibrarian.net/navon/page.jsp?paperid=2984458&searchTerm=pilps+phase+2
 

respondido por dlara (1,780 puntos) Nov 20, 2013
Licencia Creative Commons
Este obra está bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 2.5 México.

powered by UCIM

...