Materia	Carrera	Plan	Año	Periodo
(MATERIA OPTATIVA II) TEORÍA ESTRUCTURAL DE GRAFOS	LIC.EN CS.MAT.	09/17	2020	1° cuatrimestre

Docente	Función	Cargo	Dedicación
JAUME, DANIEL ALEJANDRO	Prof. Responsable	P.Tit. Exc	40 Hs

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.

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.

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.

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.

En vista a las condiciones de virtualidad en la que se dictará la asignatura se opta por un sistema de evaluación continua a través de la entrega semanal de ejercicios evaluados de 0 a 10.
Esta materia no es promocional ni se puede rendir libre. El examen final consistirá en una tesina sobre temas realcionados a la materia, la cual debe ser defendida por el alumno en una mesa de examen habitual.

[1] Diestel, R., Graph Theory, Springer.
[2] Tutte, W.T., Graph Theory, Cambridge Mathematical Library.
[3] Chartrand, Lesniak y Ping, Graphs & digraphs. Wiley
[4] Videos desarrollados por el Dr. Daniel A. Jaume, disponibles de forma pública en el canal youtube https://www.youtube.com/user/djaumester

[1] Godsil, C., Royle, G., Algebraic Graph Theory, Springer.

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.

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.