Ministerio de Cultura y Educación
Universidad Nacional de San Luis
Facultad de Ciencias Físico Matemáticas y Naturales
Departamento: Matematicas
Área: Matematicas
(Programa del año 2018)
I - Oferta Académica
Materia Carrera Plan Año Periodo
(MATERIA OPTATIVA II) TEORÍA ESTRUCTURAL DE GRAFOS LIC.EN CS.MAT. 03/14 2018 1° cuatrimestre
II - Equipo Docente
Docente Función Cargo Dedicación
PASTINE, ADRIAN GABRIEL Prof. Responsable P.Adj Exc 40 Hs
III - Características del Curso
Credito Horario Semanal Tipificación Duración
Teórico/Práctico Teóricas Prácticas de Aula Práct. de lab/ camp/ Resid/ PIP, etc. Total C - Teoria con prácticas de aula Desde Hasta Cantidad de Semanas Cantidad en Horas
Periodo
12 Hs.  Hs.  Hs.  Hs. 12 Hs. 1º Cuatrimestre 19/03/2018 22/06/2018 15 180
IV - Fundamentación
La Teoría Estructural de Grafos es una de las áreas más clásicas de la Teoría de Grafos. Estudia problemas como matchings, independencia, cobertura, empaquetamiento, conectividad, planaridad y hamiltonicidad. Todas estás propiedades tienen bastas aplicaciones en variadas ramas de la ciencia, como biología, informática, sociología, entre otras. Al mismo tiempo, son las herramientas básicas que se usan para entender y demostrar teoremas en otras áreas de la Teoría de Grafos.
V - Objetivos
El objetivo de este curso es introducir a los estudiantes a la Teoría Estructural de Grafos. Se buscará familiarizarlos con los conceptos básicos de dicha teoría y con sus aplicaciones a otras áreas de la Teoría de Grafos, relacionadas con los problemas investigados por docentes del Departamento de Matemáticas de la Universidad Nacional de San Luis.
VI - Contenidos
Unidad 1, Nociones Básicas: Grafos. El grado de un vértice. Caminos y ciclos. Conectividad. Árboles y bosques. Grafos bipartitos. Contractiones y menores. Tours de Euler. Algebra Lineal. Otras nociones de Grafos.
Unidad 2, Matching, Cobertura y Empaquetamiento: Matching en grafos bipartitos. Matching en grafos en general. Empaquetamiento y cobertura. Empaquetamiento de árboles y arboricidad. Cobertura por caminos.
Unidad 3, Conectividad: Grafos y subgrafos 2-conectados. Estructura de grafos 3-conectados. El Teorema de Menger. El Teorema de Mader. Vínculación de vértices.
Unidad 4, Ciclos de Hamilton: Condiciones suficientes sencillas. Ciclos de hamilton y secuencia de grados. Ciclos de hamilton en el grafo cuadrado.
Unidad 5, Grafos Aleatorios: La noción de grafo aleatorio. El método probabilistico. Propiedades de casi todo grafo. Funciones umbral y segundos momentos.

VII - Plan de Trabajos Prácticos
Los trabajos prácticos consistirán en ejercicios seleccionados de las secciones de ejercicios propuestos del libro Graph Theory, Diestel R., Springer. 2006. Dichos ejercicios responden a las expectativas del curso.
VIII - Regimen de Aprobación
Los alumnos deben realizar entregar los trabajos prácticos, presentación de monografía y examen final.
IX - Bibliografía Básica
[1] - Diestel, R., Graph Theory, Springer.
[2] - Tutte, W.T., Graph Theory, Cambridge Mathematical Library.
[3] - Godsil, C., Royle, G., Algebraic Graph Theory, Springer.
X - Bibliografia Complementaria
 
XI - Resumen de Objetivos
El objetivo de este curso es introducir a los estudiantes a la Teoría Estructural de Grafos. Se buscará familiarizarlos con los conceptos básicos de dicha teoría y con sus aplicaciones a otras áreas de la Teoría de Grafos, relacionadas con los problemas investigados por docentes del Departamento de Matemáticas de la Universidad Nacional de San Luis.
XII - Resumen del Programa
Unidad 1, Nociones Básicas: Grafos. El grado de un vértice. Caminos y ciclos. Conectividad. Árboles y bosques. Grafos bipartitos. Contractiones y menores. Tours de Euler. Algebra Lineal. Otras nociones de Grafos.
Unidad 2, Matching, Cobertura y Empaquetamiento: Matching en grafos bipartitos. Matching en grafos en general. Empaquetamiento y cobertura. Empaquetamiento de árboles y arboricidad. Cobertura por caminos.
Unidad 3, Conectividad: Grafos y subgrafos 2-conectados. Estructura de grafos 3-conectados. El Teorema de Menger. El Teorema de Mader. Vínculación de vértices.
Unidad 4, Ciclos de Hamilton: Condiciones suficientes sencillas. Ciclos de hamilton y secuencia de grados. Ciclos de hamilton en el grafo cuadrado.
Unidad 5, Grafos Aleatorios: La noción de grafo aleatorio. El método probabilistico. Propiedades de casi todo grafo. Funciones umbral y segundos momentos.
XIII - Imprevistos