Teoría de Grafos Curso 10/11
De Königsberg . . . . . . . . . . . . . . . . .	...................................	. . . a los multiprocesadores

Introducción

Programa

• Nociones básicas. Tipos de grafos. Isomorfismo de grafos. Representación de grafos
        en el ordenador.
• Arboles, árboles generadores, árboles generadores mínimos. Búsquedas en un grafo.
• Caminos y distancia en grafos. Algoritmos de Dijkstra, Ford y Floyd.
• Redes de transporte. Flujos en redes
• Emparejamientos en grafos bipartidos. Emparejamientos en grafos generales.
• Grafos eulerianos. Caracterizaciones y algoritmos. Problema del cartero. Digrafos
        eulerianos: digrafos de De Bruijn.
• Grafos hamiltonianos. Problema del viajante: algoritmos aproximados.
• Planaridad. Algoritmos de detección de la planaridad. Parámetros de planaridad.
• Coloración de grafos. Algoritmos de coloración. Coloración de grafos planos.
• Complejidad. Problemas NP en grafos.
• Visualización y trazado de grafos.

Bibliografía

Libros básicos de referencia

• J. Gross, J. Yellen: "Graph Theory and its Applications" . CRC Press, (2ª ed.), 2005
• G. Hernández, "Grafos: Teoría y Algoritmos". Servicio de Publicaciones, Facultad de Informática, UPM, 2003

Libros de consulta

• J. Aldous, A. Dolan: "Networks". Wiley, 1993.
• G. Chartrand, O. R. Oellermann: "Applied and Algorithmic Graph Theory".  McGraw-Hill, 1993
• G. Chartrand,  P. Zhang: "Introduction to Graph Theory".  McGraw-Hill,  2005
  
• W. Kocay, D. Kreher: "Graphs, Algorithms and Optimization". Chapman & Hall/CRC, 2005
• K. H. Rosen: "Exploring Discrete Mathematics with Maple". McGraw-Hill, 1997
• S. Pemmaraju, S. Skiena: "Computational Discrete Mathematics". Cambridge Univ. Press, 2003.
• D. B. West: "Introduction to Graph Theory". Prentice Hall, 2000.

Enlaces en la red

http://www.dma.fi.upm.es/gregorio/grafos/enlacesgrafos.html

Profesor

• Gregorio Hernández Peñalver
Despacho 1306    

Metodología

• Clases teóricas.
• Clases de resolución de ejercicios.
• Laboratorio. En las prácticas se utilizará el programa Maple V.

   Normas de evaluación

•     Opción curso

A lo largo del curso se irán proponiendo ejercicios y problemas para resolver. Algunas de estas cuestiones se resolverán en el Laboratorio. La calificación de estos ejercicios junto con la de una prueba de control, que se realizará  hacia la mitad del cuatrimestre, constituirá el 50 % de la nota final. El restante 50 % se obtendrá de la calificación  de un examen final en la fecha determinada por Jefatura de Estudios.
 
•     Opción curso con práctica

Se requiere la realizaciónde una práctica con la implementación de uno o varios algoritmos sobre grafos. El lenguaje de implementación será libre. La aplicación debe cumplir requisitos didácticos (disponer de opción paso a paso, facilidad de uso,...). La calificación de la práctica constituirá el 40% de la nota final. El restante 60% se obtendrá, a partes iguales, de la prueba de control y del examen final de la opción anterior.

•     Opción final
  

La calificación vendrá dada en su totalidad por el examen final.