Matematicas Discretas

Teoria de Grafos
Isabel C. Márquez, Ramón A Padilla.

Contenido
1. Teoría de Grafos 1.1. Origen de la Teoría de Grafos . . . . . . . . . . . . . . . . . . . . . . 1.2. Terminología Básica . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Representación de Grafos: Matrices de Adyacencias e Incidencias . . . 1.4. Cadenas, Ciclos, Grafos Conexos . . . . . . . . . . . . . . . . . . . .1.5. Grafos Eulerianos y Grafos Hamiltonianos . . . . . . . . . . . . . . . 1.6. Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 9 14 18 22 26 28 29 33 33 41 51 58 61

1.7. Isomorfismo de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8. Árboles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.9. Propiedades de los Árboles. .. . . . . . . . . . . . . . . . . . . . . . 2. Reticulados 2.1. Relación Binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Elementos Notables. Cotas Universales. Supremo, Ínfimo. . . . . . . . 2.3. Isomorfismos. Subreticulados. Reticulados Distributivos. . . . . . . .

2.4. Representación en Reticulados. . . . . . . . . . . . . . . . . . . . . . Bibliografía

iii

IVContenido

Teoria de Grafos

Isabel C. Márquez, Ramón A Padilla.

Figuras
1.1. Ejemplo de Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Multigrafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Multigrafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4. Grafos completos K1 , K2 , K3 , K4 . . . . . . . . . . . . . . . . . .. . . 1.5. Grafo completo K5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6. Grafo Nulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 4 5 5 5 6 7 20 21 22 23 25 27 27 28 29 30 33

1.7. Grafo Regular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8. Subgrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.9. Dodecaedro . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.10. Ciclo simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.11. Ciclo euleriano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.12. Secuencias gráficas para hallar un ciclo euleriano . . . . . . . . . . . . 1.13. Ejemplo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.14.Isomorfismo de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 1.15. Isomorfismo de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 1.16. Un Árbol no Conexo . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.17. Árboles Generadores y No Generadores . . . . . . . . . . . . . . . . . 1.18. Aplicación del Lema 1.9.2 . . . . . . . . . . . . . . . . . . . . . . . . 2.1. RepresentacionesGráficas de Relaciones Binarias . . . . . . . . . . .

2.2. Conjuntos Parcialmente Ordenados y Conjuntos Totalmente Ordenados 36 2.3. Propiedades de las Relaciones . . . . . . . . . . . . . . . . . . . . . . 2.4. Orden de las Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . v 36 36

VI

Figuras

Teoria de Grafos

Isabel C. Márquez, Ramón A Padilla.

Capítulo 1

Teoríade Grafos
§ 1.1. Origen de la Teoría de Grafos

Leonhard Euler, matemático suizo del siglo XVIII (Basilea, Suiza, 15 de abril de 1707 - San Petersburgo, Rusia, 18 de septiembre de 1783), es reconocido como el padre de la teoría de grafos, por haber resuelto en 1736 un problema abierto de su época, conocido como el problema de los siete puentes de Königsberg (Prusia oriental en el siglo XVIII yactualmente, Kalíngrado, provincia rusa). Euler fue reconocido por la comunidad científica, como uno de los mayores de la historia, quizá comparable a Gauss o Arquímedes. La palabra "grafo"tal como la conocemos en la actualidad, fue utilizada por primera vez en 1878 en un trabajo del matemático inglés James Sylvester, publicado en Nature [1]. En los siglos XVIII y XIX otros problemas influyeron...