Temario

TEMARIO

1. Gráficas y subgráficas.

• Gráficas y gráficas simples.
• Isomorfismos entre gráficas.
• Matrices de incidencia y adyacencia.
• Subgráficas.
• Grado de un vértice.
• Trayectorias y conexidad.
• Ciclos.

2. Árboles.

• Árboles.
• Aristas de corte.
• Vértices de corte.
• Fórmula de Cayley.

3. Conexidad.

• Conexidad.
• Bloques.
• Construcción de una red de comunicación confiable.

4. Recorridos eulerianos y ciclos hamiltonianos.

• Paseos eulerianos.
• Cíclos hamiltonianos.

5. Apareamientos.

• Apareamientos.
• Apereamientos y cubiertas de una gráfica bipartita.
• Apareamientos perfectos.

6. Coloración de aristas.

• Número cromático de aristas.
• Teorema de Vizing.
• El problema de los horarios.

7. Coloración de vértices.

• Número cromático.
• Teorema de Brook.
• Conjetura de Hajó.
• Polinomio cromático.
• Cuello y número cromático.

8. Gráficas planares.

• Gráficas planas y planares.
• Gráficas duales.
• Fórmula de Euler.
• Puentes.
• Teorema de Kuratowski.
• Teorema de los cinco colores.
• Teorema de los cuatro colores.
• Gráficas planares no hamiltonianas.