Teoría de grafos
Puntaje: 3 puntos (Lic. y Prof.)
Correlatividades: Prácticas de Análisis II y final de Álgebra Lineal.
Carga horaria: 3 hs. (clases teórico-prácticas)
Carreras: Licenciatura en Matemática (Or. Pura y Aplicada), Profesorado en Matemática
http://mate.dm.uba.ar/~spuddu/teo_de_grafos/
Breve descripción del curso:
1. Antecedentes históricos. Circuitos Eulerianos. Circuitos hamiltonianos. Coloreo de mapas.
2. Grafos y digrafos. Paseos, caminos y circuitos. Grafo completo, bipartito. Grafo conexo. Grafo regular. Subgrafo. Isomorfismo. Arboles.
3. Árboles. Definiciones equivalentes de árbol. Teoremas relativos a árboles. Árboles con raíz. Enumeración de árboles binarios. Enumeración de spanning trees de Kn. Depth-first search. Breadth-first search. Algoritmo de Prim. Algoritmo de Dijkstra. Método de Bellman.
4. Conectividad. Vértices de corte. Ramas de corte. Bloques. Conectividad k. Conectividad l. Teorema de Whitney. Teorema de Menger y sus variantes. Teorema de Ford y Fulkerson. Teorema de Koenig. Teorema de Hall.
5. Grafos planares. Teorema de Euler. No planaridad de K5 y K3,3 . Teorema de Kuratowski. Algoritmo para detectar planaridad.
6. Coloreo de vértices. Número cromático. Algoritmo. Teorema de Brooks. Teorema de Heawood. Coloreo de ramas. Algoritmo. Teorema de Vizing.
