Grado en Ingeniería Informática

MATEMÁTICA  DISCRETA II        Curso 11-12

CURSO SEMESTRE SEMESTRE no principal CARÁCTER ECTS GRUPOS
Segundo 3 4 Obligatoria 3 3S1M 3S2M-1 3S2M-2

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

PROGRAMA

Tema 1. Nociones básicas de grafos 
-    Nociones generales. Representación de grafos.
-    Subgrafos. Operaciones con grafos. Isomorfismo de grafos
-    Recorridos y caminos en grafos. Conexión. Vértices-corte y aristas puente.

Tema 2. Árboles y distancias.
-    Á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.
-    Conectividad por vértices y aristas.

Tema 3. Complejidad de algoritmos.
-    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
-    Grafos eulerianos. Caracterización.
-    Algoritmos de construcción de recorridos eulerianos. Problema del cartero.
-    Grafos hamiltonianos. Propiedades.
-    Problema del viajante. Algoritmos aproximados.

Tema 5. Planaridad y Coloración de grafos.
-    Trazado de grafos. Grafos planos. Fórmula de Euler y consecuencias. Teorema de Kuratowski.
-    Independencia  y coloración. Número cromático.
-    Algoritmos de coloración de vértices.
-    Coloración de aristas.
-    Coloración de mapas. Teorema de los cuatro colores

Tema 6. Funciones generatrices. 
-    Funciones generatrices y problemas de recuento.
-    Series de potencias. Propiedades algebraicas. Fracciones simples.
-    Resolución de relaciones de recurrencia por funciones generatrices.



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

 Se encuentran en la Guía de Aprendizaje de la asignatura

PROFESORES

    Gregorio Hernández Peñalver
    Gloria Sánchez Torrubia
    Nieves Castro González
    Victoria Zarzosa Rodríguez
   

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 febrero de 2011