Antecedentes históricos. Circuitos Eulerianos. Circuitos hamiltonianos. Coloreo de mapas.
Grafos y digrafos. Paseos, caminos y circuitos. Grafo completo, bipartito. Grafo conexo. Grafo regular. Subgrafo. Isomorfismo. Arboles.
Á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. Algoritmo de Kruskal.
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.
Grafos planares. Teorema de Euler. No planaridad de K5 y K3,3 . Teorema de Kuratowski. Algoritmo para detectar planaridad.
Coloreo de vértices. Número cromático. Algoritmo. Teorema de Brooks. Teorema de Heawood. Coloreo de ramas. Algoritmo. Teorema de Vizing.
BIBLIOGRAFIA
[1]
J. Gross and Jay Yellen, Graph Theory and its Applications, CRC, 1999.
[2]
N. L. Biggs et al, Graph Theory 1736-1936, Oxford U. Press, 1998.
A la página de la materia