P1141213 - Teoría de Grafos (Módulo II: Materias Optativas) - Curso 2013/2014

Información

• Créditos ECTS
• Créditos ECTS: 3.00
• Total: 3.0
• Horas ECTS
• Clase Expositiva: 9.00
• Clase Interactiva Laboratorio: 6.00
• Clase Interactiva Seminario: 6.00
• Horas de Titorías: 3.00
• Total: 24.0

Outros Datos

• Tipo: Materia Ordinaria Máster RD 1393/2007
• Departamentos: Xeometría e Topoloxía
• Áreas: Xeometría e Topoloxía
• Centro: Facultade de Matemáticas
• Convocatoria: 2º Semestre de Titulacións de Grao/Máster
• Docencia e Matrícula: Primeiro Curso (1º 1ª vez)

Profesores

Nome	Coordinador
Alcalde Cuesta, Fernando.	SI

Horarios

Nome	Tipo Grupo	Tipo Docencia	Horario Clase	Horario exames
Grupo /CLE_01	Ordinario	Clase Expositiva	SI	SI
Grupo /CLIL_01	Ordinario	Clase Interactiva Laboratorio	SI	NON
Grupo /CLIS_01	Ordinario	Clase Interactiva Seminario	SI	NON
Grupo /TI-ECTS01	Ordinario	Horas de Titorías	NON	NON

Programa

Existen programas da materia para os seguintes idiomas:

Castelán

Galego

Inglés

Obxectivos da materia
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.


Contidos
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.
Teoría da evolución: selección, deriva, mutación e migración. Proceso de Moran. Procesos estocásticos sobre grafos. Taxas de fixación: exemplos. Equilibrio e teorema de circulación. Supresores e amplificadores selectivos.


Bibliografía básica e complementaria
J. M. Aldous, R. J. Wilson, Graphs and applications : an introductory approach. Springer, London, 2006.
N. L. Biggs, Matemática discreta. Ed. Vicens Vives, Barcelona, 1994.
N. L. Biggs, E. K. Lloyd, R. J. Wilson, Graph Theory: 1736-1936. Clarendon Press, Oxford, 1976.
B. Bollobás, Graph Theory. Springer, New York, 1979.
E. Bujalance et al., Elementos de Matemáticas Discretas. Sanz y Torres, Madrid, 1993.
V. Chachra, P. M. Ghare, J. M. Moore, Applications of graph theory algorithms. North Holland, New York, 1979.
N. Christofides, Graph Theory: An Algorithmic Approach. Academic Press, London, 1975.
R. Diestel, Graph theory. Springer, New York, 1997.
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.
D. Jungnickel, Graphs, networks and algorithms. Springer, Berlin,1999
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.
R. J. Wilson, Introduction to graph theory. Oliver & Boyd, Edinburgh, 1972.

Competencias
Capacidade para o razoamento lóxico-matemático. Capacidade para realizar demostracións lóxico-matemáticas. Capacidade para transformar ideas e enunciados informais en enunciados formais e viceversa. Capacidade para aplicar os coñecementos adquiridos á resolución de problemas teórico-prácticos. Capacidade para enfrontarse a problemas mediante as estratexias e técnicas empregadas anteriormente.
Metodoloxía da ensinanza
Se combinarán as clases teóricas e prácticas favorecendo a participación activa dos estudantes. Realizaranse controles periódicos da aprendizaxe mediante a resolución de problemas e a realización de traballos.

Sistema de evaluación
Avaliación continuada baseada no traballo de cada alumno na aula e avaliación final mediante unha proba escrita fixada no calendario oficial da facultade. Unha avaliación continuada positiva eximirá da realización do exame final. A proba escrita consistirá en varias cuestións teóricas, que poden incluír a definición de conceptos, o enunciado de resultados e a proba total ou parcial dos mesmos, e varios problemas análogos aos resoltos no curso.



Tempo de estudo e traballo persoal
Horas presenciais:

Clases Expositivas: 9.00
Clase Interactivas: 12.00

Horas de Titorías: 3.00

Horas de traballo autónomo individual ou en grupos:

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

TOTAL: 63 horas de traballo para o alumno