Ministerio de Cultura y Educación
Universidad Nacional de San Luis
Facultad de Ciencias Físico Matemáticas y Naturales
Departamento: Matematicas
Área: Matematicas

Imprimir

Versión PDF

(Programa del año 2018)

I - Oferta Académica

Materia	Carrera	Plan	Año	Periodo
(OPTATIVA) TEORÍA ESTRUCTURAL DE GRAFOS	PROF.MATEM.	21/13	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
Teórico/Práctico	Teóricas	Prácticas de Aula	Práct. de lab/ camp/ Resid/ PIP, etc.	Total	Periodo	Desde	Hasta	Cantidad de Semanas	Cantidad en Horas
6 Hs.	Hs.	Hs.	Hs.	6 Hs.	1º Cuatrimestre	19/03/2018	22/06/2018	15	90

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.

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 / Resultados de Aprendizaje
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.

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 y rendir un coloquio teórico/práctico

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
[1]

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.

XII - Resumen del Programa

XIII - Imprevistos

XIV - Otros