Perfilado de sección

  • Caminos y ciclos Hamiltonianos (Sección 6.2 de las notas). 

    Grafos planos y característica de Euler (Sección 6.4 de las notas)

    Fecha límite para la quinta entrega: 13/7

    Teórico del lunes: Dimos una demostración alternativa del Teorema de Euler. Definimos camino y ciclo Hamiltoniano, vimos algunos ejemplos de grafos que los admiten o no y enunciamos un teorema que da condiciones necesarias y suficientes para la existencia. Por último definimos la noción de grafo plano, región y grado de una región.

    Teórico del miércoles: Demostramos el teorema de la fórmula de Euler para grafos planos conexos sin lazos. Observamos que los grafos planos pueden verse como grafos esféricos. Definimos la noción de subdivisión elemental y lo que significa que dos grafos sean homeomorfos. A partir de algunas observaciones concluimos que la fórmula de Euler es cierta también para grafos conexos con lazos o multigrafos en general. Luego mostramos que el grafo bipartito K_3,3 no es plano (quedó como ejercicio ver que el grafo completo de cinco vértices tampoco lo es). Por último enunciamos el teorema de Kuratowski que caracteriza todos los grafos planos.

    Práctico: Trabajamos sobre los ejercicios 2, 3 y 4 del práctico 7.