Teoría de Grafos

El objetivo general de la materia es proporcionar al alumno un conjunto de conocimientos propios de la matemática discreta, concretamente de la teoría de grafos, de gran utilidad teórica y práctica en diversos campos científicos. El punto de vista es multidisciplinar y aúna técnicas combinatorias, algorítmicas, topológicas, geométricas y probabilísticas abordando tanto problemas clásicos, como otros más novedosos.

1. GRAFOS.
Conceptos básicos y motivaciones. Caminos y ciclos. Conexión. Árboles. Representaciones matriciales. Grupos de automorfismos y grafos de Cayley.

2. PROPIEDADES BÁSICAS.
Conectividad. Traversabilidad: grafos eulerianos y hamiltonianos. Factorización. Elementos de algoritmia.

3. DINÁMICA EVOLUTIVA SOBRE GRAFOS.
Deriva y selección natural. Proceso de Moran clásico: probabilidad y tiempo medio de fijación. Proceso de Moran sobre grafos. Teorema de circulación. Amplificadores y supresores da selección natural. Dinámica evolutiva de redes biológicas y tecnológicas.

Bibliografía básica
J. M. Aldous, R. J. Wilson, Graphs and applications : an introductory approach. Springer, London, 2006.
R. Diestel, Graph theory. Springer, New York, 1997.
D. Jungnickel, Graphs, networks and algorithms. Springer, Berlin,1999.
R. J. Wilson, Introduction to graph theory. Oliver & Boyd, Edinburgh, 1972.

Bibliografía complementaria
N. Christofides, Graph Theory: An Algorithmic Approach. Academic Press, London, 1975.
R. P. Grimaldi, Matemáticas discreta y combinatoria. Una introducción con aplicaciones. Addison Wesley Iberoamericana, México, 1997.
N. Hartsfield, G. Ringel, Pearls in Graph Theory. Academic Press, San Diego, 1994.
J. Lovász, J. Pelikán, K. Vesztergombi, Discrete mathematics. Springer, New York, 2003.
R. Lyons, Y. Peres, Probability on trees and networks. Draft version, 2008.
M. A. Nowak, Evolutionary Dynamics. Harvard University Press, Cambridge MA, 2006.

Además de todas las competencias genéricas contempladas en la Memoria de la Titulación,

- conocer los conceptos básicos de la teoría de grafos,

- conocer métodos para resolver problemas sobre grafos,

- ser capaces de aplicar esos métodos al estudio de los problemas evolutivos.

Las “clases expositivas” combinarán aspectos teóricos y prácticos de la materia y las “clases interactivas de laboratorio” se centrarán en el estudio de los ejemplos y la resolución de algunos problemas.

Realización de un trabajo personal como la descripción de un algoritmo o la lectura de un artículo de investigación o prueba final que puede incluir cuestiones teóricas, definición de conceptos, enunciado y prueba de resultados o resolución de ejercicios y problemas.

Horas presenciales:

Clases Expositivas: 10.00
Clase Interactivas: 12.00

Horas de Tutorías: 2.00

Horas de trabajo autónomo individual:

24 horas de estudio teórico y práctico relacionado con la docencia presencial
56 horas de preparación de trabajos y de la prueba final

TOTAL: 80 horas de trabajo para el alumno