TEORIA DE GRAFOS
Objetivos
Este módulo teórico-práctico es un curso introductorio, cuyo objetivo principal es presentar el material básico, familiarizando al estudiante con el lenguaje, técnicas de demostración y algunas aplicaciones de los grafos. Se señalan también sus relaciones con otros módulos ofertados por el Departamento, aunque es básicamente autocontenido.
Programa Teoría
1.- Definiciones y conceptos básicos.
Grafos y digrafos. Isomorfismos. Matrices de incidencia y adyacencia. Subgrafos. Grado de un vértice. Cadenas, caminos y circuitos.
2.- Accesibilidad y conectividad.
Introducción. Matrices de accesibilidad y acceso. Cálculo de las componentes fuertemente conexas. Bases. Cortaduras de vértices y de aristas. Bloques. Algoritmo DFS.
3.- Árboles.
Definiciones y caracterizaciones. Ciclos fundamentales. Fórmula de Cayley. Generación de todos los árboles generadores. Complejidad algorítmica: Introducción. Árbol generador de mínimo peso. Algoritmo de Kruskal. Algoritmo de Prim.
4.- Caminos más cortos.
Introducción. Ecuaciones de Bellman. Costes no negativos: Algoritmo de Dijkstra. Costes generales: Algoritmo de Bellman-Ford. Grafos acíclicos. Método del camino crítico.
5.- Acoplamientos.
Definiciones. Acoplamientos y recubrimientos en grafos bipartidos. Teorema de Hall. Teorema de König. Teorema de Mendelsohn-Dulmage. El problema de asignación óptima. Problemas de acoplamientos en grafos cualesquiera. Aplicaciones: Tours eulerianos.
Bibliografía
- Bondy, J.A. & Murty, U.S. (1976): "Graph Theory with Applications". Ed. MacMillan Press.
- Christofides, N. (1975): "Graph Theory: An Algorithmic Approach" Ed. Academic Press.
- Even, S. (1979): "Graph Algorithms" Ed. Computer Science Press Inc.
- Gross, J. & Yellen, J. (1998): "Graph Theory and Its Applications". Ed. CRC Press.
- Swamy, M.N. & Thulasiraman, K. (1981): "Graphs, networks and algorithms". Ed. John Wiley & Sons Inc.
- Wilson, R.J. & Watkins, J.J. (1990): "Graphs. An Introductory Approach". Ed. John Wiley & Sons Inc.
|
|
|