Herramientas
de la Matemática Discreta
El curso doctorado de Herramientas
de la Matemática Discreta, forma parte del programa de
doctorado Matemática Discreta
CRÉDITOS: 3 créditos
CARÁCTER: cuatrimestral (primer
cuatrimestre)
HORARIO: Por determinar
PROFESORADO: Mª José Chávez y Ana Diánez
PROGRAMA DE LA ASIGNATURA:
Tema 1: Generalidades
sobre grafos.
Definiciones de grafos. Representación de
grafos. Subgrafos. Morfismo entre grafos. Caminos y
recorridos. Conexión. Homeomorfismo.
Grafos infinitos.
Tema
2: Nociones de algoritmos.
Definición de
algoritmo. Eficiencia de un algoritmo. Ejemplos de algoritmos en grafos.
Tema
3: Distancias en redes.
Concepto
de distancia en grafos y redes. Matriz de distancia. El problema centro y el problema mediana.
Búsqueda del camino más corto: algoritmo de Dijkstra. Aplicaciones: localización de servicios.
Tema
4: Conectividad y
flujos en redes.
Tipos
de conexión: Conexión por vértices y conexión por aristas. Desigualdad de Whitney.
Teoremas tipo Menger. Estudio de la baja conexión: Grafos 2-conexos
y 3-conexos. Grafos dirigidos: flujos en
redes. Teorema de Ford
y Fulkerson. Relación con el Teorema de Menger.
Tema
5: Coloreado de grafos.
Número cromático de un grafo. La Conjetura de los cuatro colores. Coloreado
de mapas: Teorema de Heawood. Unicidad de grafos coloreados. El polinomio
cromático.
Tema
6: Problemas
de vigilancia.
Planteamiento
del problema. Polígonos y triangulaciones de un polígono. Teoremas de la
galería de artes para polígonos simples, polígonos ortogonales y polígonos con
agujeros. Introducción a otros problemas de vigilancia.
Bibliografía:
q
N. Biggs, Matemática Discreta, Vicens Vives,
1994.
q
F. Buckley, F.
Harary, Distance in Graphs, Addison-Wesley,
1990.
q
R. Diestel, Graph Theory, Springer-Verlag, 1996.
q
L. R. Ford, D. R. Fulkerson, Flows in Networks, Princenton,1962.
q
F. Harary, Graph Theory, Addison-Wesley, 1969.
q
J. Lipschutz,
M. Lipson, 2000
problemas resueltos de Matemática Discreta, Mc. Graw-Hill, 2004.
q
W.T. Tutte, Graph Theory, Cambrige University
Press, 2001
Para más información:
