Docencia \ Ingeniería Informática plan 96 (en extinción)

Teoría de Grafos

Introducción

La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias de la Computación. Los grafos constituyen una herramienta básica para modelizar fenómenos discretos y son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos.

En este curso se pretende completar, de un modo organizado, los conceptos y términos sobre grafos que aparecen en distintas asignaturas del currículo. En todos los temas se incidirá fundamentalmente en el tratamiento algorítmico de los problemas planteados, como se observa en el programa detallado que se expone a continuación.

Profesor

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.

Material complementario

En la siguiente página se encuentran, por temas, algunos enlaces interesantes: http://www.dma.fi.upm.es/gregorio/grafos/enlacesgrafos.html

Software desarrollado por alumnos de la Facultad de Informática: http://www.dma.fi.upm.es/gregorio/grafos/paginagrafos.html

Publicaciones y reprografía

  • G. Hernández, "Grafos: Teoría y Algoritmos", Servicio de Publicaciones, Facultad de Informática, UPM, 2003.

Bibliografía

Libros básicos de referencia

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 University Press, 2003.
  • D. B. West, "Introduction to Graph Theory", Prentice Hall, 2000.

Normas y Metodología

Metodología

La asignatura se estructura en:

  • 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.