Teoría de Grafos
Optativa de 3er curso de Ingeniería Informática
Segundo cuatrimestre
Curso 2009/2010







Descripción

La asignatura de Teoría de Grafos es una asignatura del plan de estudios de Ingeniería Informática de carácter optativo y cuatrimestral, con una asignación de 6 créditos. Está concebida como una continuación de la asignatura de Matemática Discreta que se cursó en primer curso y tiene un marcado enfoque práctico, aplicado y computacional, además de un acentuado carácter formativo.

La asignatura se plantea como respuesta a una variada serie de problemas de la "vida real" (diseño de bloques, almacenamiento de productos químicos, flujo de redes, diseño de circuitos, transporte de viajeros, asignaciones horarias o de tareas, localización de elementos interesantes como hospitales, retenes de bomberos,...), lo que le confiere el enfoque aplicado que señalamos arriba, aprendiendo el alumno, además, a buscar modelos matemáticos adecuados para gran número de situaciones diferentes, lo que suele ser muy habitual en el desarrollo profesional.

El tratamiento que se pretende dar a la asignatura es práctico pues, aparte de la resolución de ejemplos y ejercicios sobre el papel, se dedicará una parte importante de los créditos a la realización de prácticas de ordenador y a la resolución de algún problema concreto (a ser posible, extraído de un caso real). Este último (en adelante el proyecto) será distinto para cada alumno o grupo de alumnos y se valorará con el 20% de la puntuación final.

El enfoque de la asignatura es computacional, pues se insistirá en presentar algoritmos para resolver cada uno de los problemas planteados (incluso se demostrarán algunos teoremas basándose en algún algoritmo concreto) y porque, al tratar de completar el proyecto será imprescindible el uso del ordenador.

El carácter formativo de la asignatura se debe, no sólo al carácter formativo que tienen las Matemáticas en general sino, en concreto, a que el lenguaje y las herramientas que se usan en la asignatura son los habituales en gran parte de las asignaturas de la carrera y en el desarrollo profesional. 

Un aspecto importante a resaltar es la diferencia cuantitativa en la selección de ejemplos a estudiar respecto a los de la asignatura de Matemática Discreta; ya que no se tratará de buscar ejemplos que se traduzcan en grafos de unos pocos vértices (rara vez más de 10) sino que pueden tener cientos (o miles). Esto se traducirá en una diferencia cualitativa a la hora de elegir los posibles métodos de resolución del problema planteado e, incluso, la propia manera de representar el grafo.

Programa

Nociones básicas
Grafos y algoritmos
Representación de grafos
Árboles
Caminos y distancias
Conectividad
Redes y flujos
Emparejamientos y factorizaciones
Grafos planos
Coloreado de un grafo

Bibliografía

  • M.O. Albertson y J. Hutchinson: Discrete Mathematics with Algorithms. John Wiley and Sons. 1988.

  • N.L. Biggs: Matemática discreta. Ed. Vicens Vives. 1994.

  • G. Chartrand y O. Oellerman: Applied and algorithmic graph theory. McGraw-Hill, 1993.

  • R.P. Grimaldi: Matemáticas discreta y combinatoria. Addison-Wesley Iberoamericana. 1997.

  • N. Harstfield y G. Ringel: Pearls in graph theory. Academic Press, 1990.

  • J. A. McHugh: Algorithmic Graph Theory.Prentice Hall, 1990.


Metodología

Anuncios y Material

Consulte la Página de material para el curso actual.

El 20% de la calificación procederá de la realización de un proyecto (resolución de un problema extraído o similar a los de la vida real, que utilice, al menos, cientos de datos y que pueda resolverse por las técnicas explicadas en la asignatura).

El proyecto será propuesto por el profesor, aunque podría aceptarse alguno propuesto por el propio alumno.

El 80% restante de la calificación reflejará el aprovechamiento obtenido por el alumno y se medirá por medio de una prueba final (que podría exigir el uso de ordenador).

Consultar la Guía Docente

Prácticas

Para poder superar la asignatura (obtener una puntuación final igual o superior a 5), es imprescindible la asistencia a las clases prácticas.

Profesores

  • Márquez Pérez, Alberto
  • Portillo Fernández, José Ramón

Tutorías

Los horarios de tutoria y asistencia al alumnado se publicarán en el Departamento.