Embedded Files
G1 - Código 2015184 (Ver el programa como archivo adjunto)
Horario:
Martes 7-9 am. Jueves 7-9 am
Salón: 210, Edificio 404 (Yu Takeuchi).
Horario de atención: Lunes 11:00 a 12:00. Miércoles 10:00 a 12:00.
Inicio de clases 28 de Octubre de 2024
ProgTGrafos-2024-II.pdf
Algunos herramientas útiles para trabajar con grafos:
Semana 1: Introducción al curso. Definiciones Básicas. Teorema del Apretón de Manos. Lema de Sperner en el Plano.
Aplicación del Lema de Sperner en el Juego de Hex.
Semana 2: Caminatas y ciclos. Isomorfismo de grafos. Grado de un vértice. Teorema de Konig (Grafos bipartitios). Grafos Eulerianos.
Semana 3: Algoritmo de Fleury y Hierholzer. Sucesiones gráficas. Teorema de Havel-Hakimi.
Semana 4: Matriz de Adyacencia de un Grafo. Propiedades espectráles.
Semana 5: Problemas extremales en grafos. Teorema de Turán.
Semana 6: Árboles. Árboles de Expansión. Algoritmo de Kruskal y Prime.
Algoritmos para la detección de ciclos:
Semana 7: Algoritmo de búsqueda profunda. Diámetro, Radio y Excentricidad de un Grafo. Centro de un Grafo. (Examen 1)
Semana 8: Laplaciano de un Grafo. Teorema Matricial de Árboles.
Semana 9: Demostraciones de la Fórmula de Cayley. (Códigos de Prufer y Funciones)
Semana 10: Emparejamientos, Emparejamientos Perfectos. Teorema de Hall.
Semana 11: Emparejamientos Perfectos en Grafos Bipartitos. Problema del Dimero. El Pfaffiano y el número de emparejamientos perfectos.
Lectura Recomendad Algoritmo FKT.
Semana 12: Grafos Hamiltonianos.
Examen 2, Jueves Semana 12
Semana 13: El problema del agente viajero. Grafos planos.
Semana 14: Coloración de vértices. Teorema de los 5 colores. Grafos Críticos. Heurísticas para coloración de grafos. Polinomio cromático.
Semana 15: Coloración de Aristas
Examen 3, Martes Semana 16
Referencias:
R. Wilson. Introduction to Graph Theory. Pearson, Quinta Ed. 2010.
D. West. Introduction to Graph Theory. Pearson, Segunda Ed. 2001.
M. A. Henning, J H van Vuuren. Graph and Network Theory. An Applied Approach using Mathematica, Springer. 2022.
Referencias Adicionales Teoría de Grafos:
J.A. Bondy, U.S.R. Murty. Graph Theory. Graduate Texts in Mathematics, Springer, 2008.
S. M. Cioba, M. Ram Murty. A First Course in Graph Theory and Combinatorics, Texts and Readings in Mathematics, Springer, Second ed. 2022.
C. Gosdil, G. Royle. Algebraic Graph Theory, Graduate Texts in Mathematics, Springer, 2001.
Cesar O. Aguilar. An Introduction to Algebraic Graph Theory, Notas de Clase.
A próposito del último problema de la tarea, les comiendo esta lectura: APPLICATIONS OF A TECHNIQUE FOR LABELLED ENUMERATION
Lectura recomendada: Erdos-Wilson On the chromatic index of almost all graphs
Page updated
Google Sites
Report abuse