Teoría de Grafos

O obxectivo xeral da materia é proporcionar ao alumno un conxunto de coñecementos propios da matemática discreta, e concretamente da teoría de grafos, de gran utilidade teórica e práctica en diversos campos científicos. O punto de vista é multidisciplinar e combina técnicas combinatorias, algorítmicas, topolóxicas, xeométricas e probabilísticas abordando algúns problemas clásicos e outros máis novidosos.

1. GRAFOS.
Conceptos básicos e motivacións. Camiños e ciclos. Conexidade. Árbores. Representacións matriciais. Grupos de automorfismos e grafos de Cayley.

2. PROPIEDADES BÁSICAS.
Conectividade. Traversabilidade: grafos eulerianos e hamiltonianos. Factorización. Elementos de algoritmia.

3. DINÁMICA EVOLUTIVA SOBRE GRAFOS.
Deriva e selección natural. Proceso de Moran clásico: probabilidade e tempo medio de fixación. Proceso de Moran sobre grafos. Teorema de circulación. Amplificadores e supresores da selección natural. Dinámica evolutiva de redes biolóxicas e tecnolóxicas..

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.

Ademais de todas as competencias xenéricas contempladas na Memoria da Titulación,

- coñecer os conceptos básicos da teoría de grafos,

- coñecer métodos para resolver problemas sobre grafos,

- ser capaces de aplicar algún deses métodos ao estudo dos problemas evolutivos.

As “clases expositivas” combinarán aspectos teóricos e prácticos da materia e as “clases interactivas de laboratorio” se centrarán no estudo dos exemplos e na resolución dalgúns problemas.

Realización dun traballo persoal como a descripción dun algoritmo ou a lectura dun artigo de investigación ou proba final que pode incluír cuestións teóricas, definición de conceptos, enunciado e proba de resultados ou resolución de exercicios e problemas.

Horas presenciais:

Clases Expositivas: 10.00
Clase Interactivas: 12.00

Horas de Titorías: 2.00

Horas de traballo autónomo individual ou en grupos:

24 horas de estudo teórico e práctico relacionado coa docencia presencial
56 horas de preparación de exercicios e outros traballos

TOTAL: 80 horas de traballo para o alumno