MATEMÁTICA  DISCRETA II        Curso 09-10

CURSO SEMESTRE SEMESTRE no principal CARÁCTER ECTS
Segundo 3 4 Obligatoria 3


GUÍA DOCENTE
Programa
Bibliografía
Normas evaluación
Profesores
AULA VIRTUAL Ejercicios Enlaces y Software


PROGRAMA

Tema 1. Nociones básicas de grafos (4 horas)
-    Nociones generales. Representación de grafos.
-    Subgrafos. Operaciones con grafos. Isomorfismo de grafos
-    Trazado de grafos. Grafos planos. Fórmula de Euler y consecuencias. Teorema de Kuratowski.

Tema 2. Caminos, conectividad, árboles y distancias. (9 horas)
-    Recorridos y caminos en grafos. Conexión. Vértices-corte y aristas puente. Conectividad por vértices y aristas.
-    Árboles. Árboles con raíz. Búsquedas en grafos.
-    Enumeración de árboles etiquetados. Fórmula de Cayley. Código de Prüfer.
-    Árbol generador de peso mínimo: Algoritmos de Prim y Kruskal
-    Distancias en grafos. Centro y diámetro. Caminos mínimos: Algoritmos de Dijkstra, Bellman-Ford y Floyd.

Tema 3. Complejidad de algoritmos. (6 horas)
-    Notación de Knuth. Crecimiento de funciones.
-    Complejidad de algoritmos. Complejidad de problemas.
-    Análisis de la complejidad de algoritmos básicos.
-    Clases P y NP de problemas.
-    Problemas NP-completos.

Tema 4. Recorridos en grafos (6 horas)
-    Grafos eulerianos. Caracterización.
-    Algoritmos de construcción de recorridos eulerianos. Problema del cartero.
-    Grafos hamiltonianos. Propiedades.
-    Problema del viajante. Algoritmos aproximados.

Tema 5. Coloración de grafos. (6 horas)
-    Independencia, recubrimiento y coloración. Número cromático.
-    Algoritmos de coloración de vértices.
-    Coloración de aristas.
-    Polinomio cromático.
-    Coloración de mapas. Teorema de los cuatro colores

Tema 6. Funciones generatrices. (9 horas)
-    Funciones generatrices y problemas de recuento.
-    Series de potencias. Propiedades algebraicas. Fracciones simples.
-    Teorema del binomio generalizado.
-    Resolución de relaciones de recurrencia por funciones generatrices.
-    Funciones generatrices exponenciales.




BIBLIOGRAFÍA
Referencias básicas

-    N. Biggs: “Discrete Mathematics”, 2nd ed. Oxford Univ. Press, 2002.
-    J. Gross, J. Yellen: “Graph Theory and its Applications”. CRC Press, 1999
-    G. Hernández, “Grafos: Teoría y Algoritmos”. Servicio de Publicaciones, Facultad de Informática, UPM, 2006

Libros de consulta
-    G. Chartrand,  P. Zhang: “Introduction to Graph Theory”.  McGraw-Hill,  2005
-    F. García Merayo, G.  Hernández  y A. Nevot: “Problemas resueltos de Matemática Discreta”. Ed. Thomson-Paraninfo, 2003
-    R. Grimaldi: Matemáticas Discreta y Combinatoria, Addison-Wesley, 1997.
-    W. Kocay, D. Kreher: “Graphs, Algorithms and Optimization”. Chapman & Hall/CRC, 2005
-    J. Matousek, J. Nesetril: “Invitación a la matemática discreta”. Reverté, 2008
-    D. B. West: “Introduction to Graph Theory”. Prentice Hall, 2001.
-    H. Wilf: “Generatingfunctionology”, 3rd ed. A. K. Peters, 2005




NORMAS DE EVALUACIÓN

Evaluación continua

•    Pruebas de evaluación escritas, que combinarán respuestas cortas y largas. Se efectuarán dos pruebas y cada una representará el 30% de la nota final.

•    Resolución de ejercicios en clase y en laboratorio. Constituirá el 20% de la nota final.

•    Realización y exposición pública de trabajos en grupo. Constituirá el 20% de la calificación.

Evaluación final
En la fecha que determine la Dirección del Centro


PROFESORES

    
Gregorio Hernández Peñalver


RECURSOS EN LA RED

Se utilizará de forma intensiva la plataforma Moodle en Aula Virtual, para proporcionar material de estudio y ejercicios a los estudiantes.


Enlaces con material y recursos.


Software sobre Grafos con animaciones de algoritmos


EJERCICIOS (Hojas de ejercicios y problemas de la asignatura)


Actualizado en septiembre de 2009