Download 42998318_0708

__________________________________________________________________________
Curso:
2007-2008
Centro:
ESCUELA POLITÉCNICA SUPERIOR
Estudios:
INGENIERÍA DE INFORMÁTICA DE SISTEMAS
Asignatura:
TEORÍA DE GRAFOS Y APLICACIONES
Código:
42998318
Ciclo:
2º
Curso:
1º
Cuatrimestre:
1º
Carácter:
OPTATIVA
Créditos teóri.: 3
Créditos práct.: 3
Profesor/es:
JOSÉ CÁCERES GONZÁLEZ
Area:
MATEMÁTICA APLICADA
Departamento: ESTADÍSTICA Y MATEMÁTICA APLICADA
__________________________________________________________________________
I. TEMARIO.
Tema 1. GRAFOS Y ALGORITMOS
Conceptos básicos. Grado y secuencias de grados. Representaciones en memoria. Dos algoritmos
fundamentales: BFS y DFS. Álgebra de grafos. Grafos importantes. Conectividad de un grafo.
Complejidad algorítmica.
Tema 2. CAMINOS
Distancia en un grafo. Excentricidad, centro, radio, periferia, diámetro, distancia total, mediana.
Algoritmos de distancia: Dijkstra, Ford y Floyd. Grafos eulerianos. Problema del cartero chino y
eulerizaciones sencillas. Grafos hamiltonianos. Algoritmos de aproximación del TSP.
Tema 3. DIGRAFOS
Diferentes tipos de conexión de un digrafo. Algoritmo de orientación fuerte de un grafo. DAG’s
y algoritmo de ordenación topológica. Caminos críticos. Conjuntos estables y absorbentes.
Núcleo de un digrafo y su aplicación al análisis de juegos.
Tema 4. FLUJO EN REDES
Redes. Flujos. Capacidades de arco. Principio de optimalidad de Bellman. Flujos máximos.
Cortes. Teorema del máximo flujo-mínimo corte. Variaciones del problema original.
Tema 5. EMPAREJAMIENTOS, RECUBRIMIENTO Y COLOREADO
Emparejamientos, caso bipartito. Emparejamientos en el caso general. Matrimonio estable.
Recubrimiento de vértices y aproximación por dualidad. Coloreado, número cromático.
Algoritmos de aproximación. Aplicaciones del coloreado.
II. BIBLIOGRAFIA.
1. N.L. Biggs. Matemáticas Discretas. Ed. Vicens Vives, 1994.
2.
3.
4.
5.
6.
7.
8.
9.
N. Christofides. Graph Theory, an algorithmic approach. Academic Press.
R. Diestel. Graph Theory. Springer-Verlag, 1997.
R.P. Grimaldi. Matemática Discreta y Combinatoria. Addison-Wesley Iberoamericana, 1989.
J. Gross y J. Yellen. Graph Theory and its applications. 1998.
L. Lovász, J. Pelikán y K. Vesztergombi. Discrete Mathematics Elementary and Beyond.
Springer-Verlag, 2003.
O. Ore. Grafos y sus aplicaciones. Euler, 1995.
S. Pemmaraju y S. Skiena. Computational Discrete Mathematics: Combinatorics and Graph
Theory with Mathematica. Cambridge University Press, 2003.
R.J. Trudeau. Introduction to Graph Theory. Dover, 1993.
42998318_0708.doc
/1
III. MÉTODO DE EVALUACIÓN
Para superar la asignatura, el alumno deberá realizar un examen al final de la misma. Podrá completar
esta nota con la realización de trabajos y/o prácticas.
42998318_0708.doc
/2