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

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 Tutorías: 3.00
• Total: 24.0

Otros Datos

• Tipo: Materia Ordinaria Máster RD 1393/2007
• Departamentos: Geometría y Topología
• Áreas: Geometría y Topología
• Centro: Facultad de Matemáticas
• Convocatoria: 2º Semestre de Titulaciones de Grado/Máster
• Docencia y Matrícula: null

Profesores

Nombre	Coordinador
Alcalde Cuesta, Fernando.	SI

Horarios

Nombre	Tipo Grupo	Tipo Docencia	Horario Clase	Horario exámenes
Grupo CLE01	Ordinario	Clase Expositiva	SI	NO
Grupo CLIL_01	Ordinario	Clase Interactiva Laboratorio	SI	NO
Grupo CLIS_01	Ordinario	Clase Interactiva Seminario	SI	NO
Grupo TI-ECTS01	Ordinario	Horas de Tutorías	NO	NO

Programa

Existen programas da materia para los siguientes idiomas:

Castellano

Gallego

Inglés

Objetivos de la asignatura
El objectivo 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.
Contenidos
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.
Teoría de la evolución: selección, deriva, mutación y migración. Proceso de Moran. Procesos estocásticos sobre grafos. Tasas de fijación: ejemplos. Equilibrio y teorema de circulación. Supresores y amplificadores selectivos.

Bibliografía básica y 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
Capacidad para el razonamiento lógico-matemático. Capacidad para realizar demostraciones lógico-matemáticas. Capacidad para transformar ideas y enunciados informales en enunciados formales y viceversa. Capacidad para aplicar los conocimientos adquiridos a la resolución de problemas teórico-prácticos. Capacidad para enfrentarse a problemas mediante las estrategias y técnicas empleadas con anterioridad.


Metodología de la enseñanza
Se combinarán las clases teóricas y prácticas, favorecendo la participación activa de los estudantes. Se realizarán controles periódicos del aprendizaje mediante la resolución de problemas y la realización de trabajos.


Sistema de evaluación
Evaluación continua basada en el trabajo de cada alumno en clase y evaluación final mediante una prueba escrita fijada en el calendario oficial de la facultad. Una evaluación continua positiva eximirá de la realización del exame final. La prueba escrita consistirá en varias cuestiones teóricas, que pueden incluir la definición de conceptos, el enunciado de resultados y la prueba total o parcial de los mismos, así como varios problemas análogos a los resueltos en el curso.


Tiempo de estudio y trabajo personal
Horas presenciales:

Clases Expositivas: 9.00
Clase Interactivas: 12.00

Horas de Tutorías: 3.00

Horas de trabajo autónomo individual o en grupo:

18 horas de estudio teórico y práctico relacionado con la docencia presencial
24 horas de preparación de ejercicios y otros trabajos

TOTAL: 63 horas de trabajo para el alumno