| Clase 1: |
- Introducción - Motivación.
- Fundamentos básicos de la Teoría de Grafos.
|
| Clase 2 a 4: |
- Conectividad en Grafos:
- Componentes conexas de un grafo; conjuntos de separación;
conjuntos de corte; nodo de articulación; arista puente.
- Definiciones de k-arista-conectividad, k-nodo-conectividad y relación
entre ellas.
- Caracterización de topologías de cubrimiento minimales (árboles).
- Teorema de Mader (condición suficiente de k-conectividad).
- Contracción en un grafo.
- Redes 2-conexas:
- Caracterización
- Operaciones que preservan la 2-conexidad
- Aplicación en modelos topologicamente robustos.
- Caso Particular: Ciclos Hamiltoneanos.
- Redes 3-conexas:
- Caracterización (Teorema de Tutte),
- Operaciones que preservan la 3-conexidad.
- Aplicación en modelos topologicamente robustos
- El Teorema de Menger.
- Teorema de Ford-Fulkerson y su aplicación para la determinación
de un conjunto de corte en un grafo.
- Condición necesaria y suficiente para la existencia de k árboles de cubrimiento
arista-disjuntos en un grafo (Teorema de Tutte-Nash-Williams).
|
| Clase 5 a 7: |
- Diseño de redes con niveles de sobrevivencia prefijados:
- Definición de la k-nodo-(resp. arista)-sobrevivencia respecto a un conjunto
distinguido de nodos de una red.
- Problemas:
- ECON - Encontrar la sub-red de costo mínimo que satisfaga ciertos
requerimientos de arista-sobrevivencia preestablecidos.
- NCON - Encontrar la sub-red de costo mánimo que satisfaga ciertos
requerimientos de nodo-sobrevivencia preestablecidos.
- Casos particulares del ECON y NCON: kNECON, kNCON, 2NCON, 2ECON, etc.
- Casos particulares del NCON/ECON resolubles en tiempo polinomial.
- Formulación del ECON y NCON como problemas de programación lineal entera.
- Condición necesaria para que una red sea k-nodo-conexa (Lema de Harary).
- Condición necesaria para que una red satisfaga requerimientos de conectividad
heterogéneos (Lema de Chou-Frank).
- Número mánimo de aristas a agregar en una red dada, de forma de alcanzar requerimientos
de conectividad preestablecidos (Teorema de Frank).
|
| Clase 8 a 10: |
- Resultados estructurales para redes con desigualdad triangular entre los costos de
los arcos:
- Modelos MWkVCSN y MWkECSN: el problema de encontrar el subgrafo
k-nodo-conexo (resp. k-arista-conexo) de costo mínimo que cubre los nodos
de un grafo completo.
-
Caso particular (k=2): modelos MW2VCSN- MW2ECSN con desigualdad triangular:
- Condiciones equivalentes para la 2-nodo-conectividad de un grafo
(Teorema de Berge).
- Existencia y estructura de una solución óptima 2-nodo-conexa para
el problema MW2VCSN (Teorema de Monma et al.).
- Condición suficiente para que una solución factible a un
problema MW2VCSN (resp. MW2ECSN) con función de distancia canónica
sea solución óptima global (Teorema de Monma et al.).
- Modelos MWkVCSN y MWkECSN con k &ge 3 y desigualdad triangular:
- Existencia y estructura de una solución óptima k-arista-conexa para
el problema MWkECSN (Teorema de Bienstock et al.).
- Existencia y estructura de una solución óptima k-nodo-conexa para
el problema MWkVCSN (Teorema de Bienstock et al.).
- Condición necesaria de una solución óptima del MWkVCSN satisfaciendo
la condicion |V| ≥ 2k (Teorema de Bienstock et al.).
|
| Clase 11 a 13: |
- Algoritmos clásicos de diseño topológico: Heurística de Steiglitz,
Heurística de Goemans-Bertsimas, etc.
-
Introducción a la Confiabilidad Estructural.
|
| Clase 14 a 15: |
- Heurísticas a medida como herramientas de diseño:
- Construcción greedy de soluciones factibles.
- Algoritmos de Búsqueda Local.
|
| Clase 16 a 24: |
- Resolución Heurística-Greedy de los problemas:
- GSP (Generalized Steiner Problem).
- STNCSP (Steiner 2-node-connected subgraph problem).
- SPG (Steiner Problem in Graphs).
- STSP (Steiner Traveling Salesman Problem).
- RSP (Ring Star Problem).
|
| Clase 25 a 26: |
- Presentación de los problemas de diseño topológico que deberían
resolver los estudiantes.
|
