CUATRIMESTRE: Segundo de 2003

HORARIO: Viernes de 16 a 20 hs.

PRIMERA CLASE: Viernes 29 de agosto 16hs.

PUNTAJE: 2 puntos

ASIGNATURAS CORRELATIVAS: Algoritmos y Estructuras de Datos III

Objetivos:

Se propone esta materia optativa que puede ser ofrecida a estudiantes de la Licenciatura y el Doctorado en Computación y en Matemática. Se requieren para poder cursarla conocimientos básicos en teoría de grafos.
Los objetivos de esta materia son diversos. Por un lado se pretende introducir a los alumnos en tópicos avanzados en teoría de grafos a fin de que puedan descubrir nuevos temas para realizar sus tesis sumándose al grupo que está trabajando en el Departamento en esta área. Por otro lado, completar la formación en grafos puede ser importante para aquellos que piensan hacer investigación en otra área pero que algunos de estos temas le pueden resultar de utilidad para su aplicación en otros campos de la Informática o de la Matemática. Por último, el familiarizarse con la metodología empleada para atacar los problemas que surgen en este tópico puede ser de utilidad para todo estudiante que tiene intenciones de dedicarse a la investigación científica.
La propuesta es realizar la materia con una modalidad de seminario, es decir que el Profesor debe introducir los temas teóricos para luego los estudiantes presentar en clase distintos trabajos de actualidad en estos temas. También se propone discutir en clase sobre algunos problemas abiertos. La materia finaliza con una evaluación final donde se haga una revisión sobre todo lo visto en el cuatrimestre.

Programa:

Unidad 1: Un repaso histórico. Conceptos básicos en grafos. Grafos dirigidos. Conectividad. Arboles. Conjunto Independiente. Matchings. Grafos Eulerianos y Hamiltonianos. Coloreo. Planaridad. Aplicaciones. Complejidad computacional.

Unidad 2: Grafos de intersección. Definición. Estudio de diferentes clases: cordales, de intervalos, clique, arco-circulares, circulares, de permutación. Aplicaciones a diversos campos: biología, psicología, computación, estadística. Discusión de problemas abiertos.

Unidad 3: Clases de grafos definidas por subgrafos prohibidos. Familias finitas e infinitas. Ejemplos de grafos que pueden ser definidos de esta manera: línea, split, de comparabilidad, soles.

Unidad 4: Grafos perfectos. Definición. Conjetura fuerte y conjetura débil. Clases de grafos perfectas y no perfectas. Clases donde vale la conjetura fuerte. Grafos minimalmente imperfectos. Caracterización de grafos perfectos por medio de teoría poliedral. Grafos clique-perfectos. Definición. Problemas resueltos y problemas abiertos en esta clase.

Bibliografía básica:

Balakrishnan R. and Ranganathan K., A textbook of graph theory, Springer-Verlag, 2000.

Brandstadt A., Bang Le V. and Spinrad J., Graph classes: A survey, SIAM, 1999.

Golumbic M., Algorithmic graph theory and perfect graphs, Academic Press, 1980.

Harary F., Graph Theory,. Addison Wesley, 1968.

McKee T. and McMorris F., Topics in intersection graph theory, SIAM, 1999.