Teoría de las Gráficas

Ilán A. Goldfeder (ilan@ciencias.unam.mx)
Pilar Alanís (pily.alanis@gmail.com)

Grupo 4274
Lunes a viernes de 8 a 9 hrs.
Salón O-222

Temario y bibliografía

Calificaciones finales

Para correcciones, comentarios y quejas, estaré yendo el miércoles, jueves y viernes durante las mañanas. Me encuentran en la cafetería o en el Cubículo Externo del Instituto de Matemáticas. También pueden escribirme a ilan@ciencias.unam.mx

El examen final es el próximo viernes 11 de diciembre a las 8.00 hrs en el salón de clases.

El viernes pueden pasar a recoger sus tareas, ya sea de 8 a 10 hrs en el salón de clases o después conmigo.

Evaluación

La calificación será el promedio de unas catorce tareas de más o menos diez preguntas cada una.

La calificación de cada pregunta consta de dos partes: la mitad de que sepamos que tenían la idea y la otra mitad de que lo hayan escrito bien.

Si obtienen menos de ocho de promedio durante el semestre, el examen final es obligatorio.

Avisos

Clase de dudas el próximo viernes 15.

Teorema 1 (Teorema de Bondy-Chvátal) Dada $G$ una gráfica con $n$ vértices, $n \geq 3$. Puedo agregar una arista a $G$ entre dos vértices no adyacentes si satisfacen la condición de Bondy-Chvátal, i.e. la suma de sus grados es mayor o igual que el número de vértices de $G$. Si $G'$ es el resultado de añadir aristas entre vértices que satisfacen la condición de Bondy-Chvátal y $G'$ tiene un ciclo hamiltoniano entonces $G$ tiene un ciclo hamiltoniano.

La condición es sobre los grados de los vértices antes de agregar la nueva arista.