Estimados estudiantes.
A continuación les paso un cronograma tentativo para la segunda parte del curso, pronto se actualizará el mismo en la página principal del curso.
Semana 1 (miércoles 02/10 al martes 08/10):
Relaciones de A en B. Representación con diagramas, con matrices y con dígrafos (este último cuando A=B).
Tipos de relaciones en un conjunto: reflexivas, irreflexivas, simétricas, antisimétricas, asimétricas, transitivas.
Problemas de conteo con relaciones.
Relaciones de equivalencia. Clases de equivalencia. Partición asociada a una clase de equivalencia ("conjunto cociente").
Aplicación a problemas de conteo.
Práctico: Práctico 6.
Semana 2 (miércoles 09/10 al martes 15/10):
Relaciones de órdenes. Conjuntos parcialmente ordenados (posets). Elementos minimales, maximales, mínimo y máximo.
Cadenas, anticadenas, altura de un elemento. Diagrama de Hasse. Propiedades del diagrama de Hasse
(la cantidad de niveles es igual al largo más alto de una cadena, los niveles forman anticadenas, etc).
Teorema de Dilworth y Teorema de Mirsky (dual del Teorema de Dilworth).
Corolario: En todo poset con N>nm elementos existe una cadena de largo n+1 o una anticadena de largo m+1.
Cotas superiores e inferiores, supremo, ínfimo, retículos.
Definiciones básicas de teoría de grafos, tipos de caminos: abiertos, cerrados, recorridos, circuitos, caminos simples (abiertos),
caminos simples cerrados o ciclos. Familias especiales de grafos: el camino simple Pn, el n-ciclo Cn, grafos completos y grafos bipartitos completos.
Distancia inducida por un grafo (puede tomar valor infinito si el grafo no es conexo) y diámetro de un grafo. Componentes conexas de un grafo.
Práctico: Prácticos 7 y 8.
Semana 3 (miércoles 16/10 al martes 22/10):
Definiciones básicas de teoría de grafos, tipos de caminos: abiertos, cerrados, recorridos, circuitos, caminos simples (abiertos), caminos simples cerrados o ciclos.
Clases especiales de grafos: el camino simple Pn, el n-ciclo Cn, grafos completos y grafos bipartitos completos. Distancia inducida por un grafo (puede tomar valor infinito si el grafo no es conexo) y diámetro de un grafo.
Isomorfismo: definición y ejemplos, propiedades que se preservan por isomorfismo. Árboles: definición y ejemplos. Teorema de existencia de hojas. Relación entre cantidad de vértices y aristas en un árbol. Teorema de unicidad de caminos simples en un árbol. Existencia de árbol recubridor para grafos conexos.
Práctico: Prácticos 8 y 9.
Semana 4 (miércoles 23/10 al martes 29/10):
Problema de los puentes de Königsberg. Recorrido y circuitos eulerianos. Condición necesaria y suficiente de existencia. Obtención del recorrido de longitud máxima en un grafo.
Caminos y ciclos hamiltonianos. Algunas condiciones necesarias de existencia.
Práctico: Práctico 9.
Semana 5 (miércoles 30/10 al martes 05/11):
Planitud: Inmersión plana, regiones, grado de una región, teorema de la suma de los grados de las regiones. Fórmula de Euler para grafos planos: v-e+r=2.
Prueba de no planitud de K(3,3) y K(5). Subdivisiones elementales, homeomorfismo de grafos. Teorema de Kuratowski (solo enunciado). Ejemplos.
Práctico: Práctico 10.
Semana 6 (miércoles 06/11 al martes 12/11):
Subdivisiones elementales, homeomorfismo de grafos. Teorema de Kuratowski (solo enunciado). Ejemplos.
Coloración propia de un grafo, el polinomio cromático y el número cromático.
Cuestionario: Cuestionario 2 disponible en plataforma eva.
Práctico: Práctico 11.
Semana 7 (miércoles 13/11 al martes 19/11):
Contracción y borrado de arista. Teorema que relaciona los polinomios cromáticos de G, Ge y G-e.
Práctico: Práctico 11 y repaso.
Semana 7.5 (miércoles 20/11, jueves 21/11):
Repaso/consulta.