Teoría de Grafos 2023-II

G1 -  Código 2015184 (Ver el programa como archivo adjunto)

Horario:

Inicio de clases 10 de Agosto de 2023

ProgTGrafos-2023-II.pdf

Algunos editores que les pueden ser de ayuda para hacer grafos:

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.

Taller en Clase (No es para entregar, pero pueden hacer un buen uso del festivo...)

Taller(MatricesdeAdyacencia).pdf

Semana 3: Sucesiones gráficas. Teorema de Havel-Hakimi. Problemas Extremales.

Resumen.pdf

Semana 4: Problemas Extremales. Teorema de Turán. Introducción a árboles.

Taller en Clase (No es para entregar)

Taller(ProblemasExtremales).pdf

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.

Taller en clase

Taller(Número de Emparejamientos).pdf

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.