Download Curso: 2009-2010 Centro: ESCUELA POLITÉCNICA SUPERIOR

Document related concepts

Grafo de intervalos wikipedia, lookup

Teorema del coloreo de carreteras wikipedia, lookup

Cortes de grafos en la visión por computador wikipedia, lookup

Algoritmo-Graphplan wikipedia, lookup

Grafo cuadrado wikipedia, lookup

Transcript
__________________________________________________________________________
Curso:
2009-2010
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_0910.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_0910.doc
/2