Presentación del grupo 4254 - 2011-1.

Seminario de Análisis Combinatorio

(Algoritmos y Heurísticas para Teoría de Gráficas)

Profesora: María De Luz Gasca Soto

luzg@ciencias.unam.mx

Horario Propuesto: 12-13 hrs, Lunes a Viernes

Iniciamos clase, Viernes 13,Cubículo 014, Departamento de Matemáticas.

Objetivo: Analizar, diseñar y programar algoritmos y heurísticas para problemas relacionados con Teoría de Gráficas, tanto en forma secuencial como paralela. Se revisaran algunos problemas NP-Completos y se desarrollaran heurísticas y algoritmos de aproximación para obtener una buena solución en tiempo polinomial.

Temario

I. Teoría de Redes

1. Flujo Máximo

2. Conexidad

3. Teorema de Menger

II. Apareamientos

1. Apareamientos en Gráficas Bipartitas

2. Apareamientos en Gráficas en General

3. Factorizaciones

4. Diseño de Bloques

III. Gráficas Eulerianas y Hamiltonianas

1. Caracterización de Gráficas Eulerianas

2. El problema del Cartero Chino

3. Digraficas Eulerianas

4. Caracterización de Gráficas Hamiltonianas

5. El problema del Agente Viajero

IV. Gráficas Planas

1. Propiedades de Gráficas Planas

2. Algoritmos para verificar la planaridad en gráficas

3. El género de una gráfica

4. Gráficas Menores

V. Coloración en Gráficas

1. Coloración en vértices

2. Polinomio Cromático

3. Coloración en Gráficas

4. El problema de los cuatro colores

VI. Etiquetación en Gráficas

1. (p,q)-Etiquetacion en Gráficas

2. (2,1)- Etiquetacion en Gráficas

3. Algoritmos y Heurísticas

4. Aplicaciones

Bibliografía

1. Chartran, G. And Oellerman, O.R.

Applied and Agorithmic Graph Theory.

Mc Graw-Hill, USA, 1993.

2. Ahuja, R.K., Magnanti, T.L. and Orlin, J.B.

Network Flows: Theory, Algorithms and Applications.

Prentince Hall, USA, 1993

3. Balakrishnan, V.K.

Graph Theory.

Mc Graw-Hill, USA, 1997.

4. Janssen, J.C.M

Channel Assignment and Graph Labeling

Wiley, 2002.

5. Reed, Bruce A. and Sales, C.L, editors.

Recent Advances in Algorithms and Combinatorics.

Springer, 2002.