Embedded Files
G1 - Código 2015184 (Ver el programa como archivo adjunto)
Horario:
Lunes 4-6 pm. Miércoles 4-6 pm
Salón: 212, Edificio 404.
Inicio de clases 10 de Agosto de 2023
ProgTGrafos-2023-II.pdf
Semana 1: ¿Teoría de Grafos? Introducción al curso.
Semana 2: Caminatas y ciclos. Isomorfismo de grafos. Grado de un vértice. Teorema de Konig (Grafos bipartitios). Grafos Eulerianos. Matriz de Adyacencia y su polinomio caractésitico.
Semana 3: Sucesiones gráficas. Teorema de Havel-Hakimi. Problemas Extremales.
Semana 4: Problemas Extremales. Teorema de Turán. Introducción a árboles.
Semana 5: Árboles de expansión. Algoritmo de Kruskal. Algoritmo de Prime. Distancia en grafos y árboles (distancia entre vértices, diámetro y radio de un grafo, excentricidad de un vértice). Índice de Wiener.
Semana 6: Laplaciano de un grafo y valores propios. Teorema Matricial para Árboles. Fórmula de Cayley. Algoritmo de búsqueda en profunidad (Depth-first search)
Semana 7: Emparejamientos; Emparejamientos máximales y máximos. Emparejamientos perfectos. Teorema de Hall. Cobertura de vértices. Teorema de Konig-Egervary.
Semana 8: El Pfafiano y Teorema de Cayley.
Miércoles Semana 8
Semana 9: Algoritmo FKT. Fórmula de Fisher, Kasteleyn, and Temperley. Grafos Hamiltonianos.
Lectura recomendada: Mathematician Answers Chess Problem About Attacking Queens.
A próposito del último problema de la tarea, les comiendo esta lectura: APPLICATIONS OF A TECHNIQUE FOR LABELLED ENUMERATION
Semana 10: Travelling Salesman Problem, TSP.
Semana 11: Grafos planos.
Examen 2, Miércoles Semana 12.
Semana 13: Coloración de vértices.
Semana 14: Heurísticas de coloración de vértices. Polinomio cromático.
Semana 15: Coloracón de Aristas.
Lectura recomendada: Erdos-Wilson On the chromatic index of almost all graphs
Referencias:
D. West. Introduction to Graph Theory. Pearson, Segunda Ed. 2001.
J.A. Bondy, U.S.R. Murty. Graph Theory. Graduate Texts in Mathematics, Springer, 2008.
M. A. Henning, J H van Vuuren. Graph and Network Theory. An Applied Approach using Mathematica, Springer. 2022.
Referencias Teoría Algebraica de Grafos:
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.
Page updated
Google Sites
Report abuse