Matemáticas (plan 1983) 2017-1

Objetivos: Los principales objetivos del presente curso son introducir al estudiante en la Teoría de gráficas y enseñarle a modelar problemas que se pueden plantear y resolver con gráficas (objetos de estudio propios de esta teoría).

Temario:

1. Gráficas

• Conceptos básicos.
• Isomorfismo de gráficas.
• Matriz de adyacencia.
• Subgráficas.
• Clases de gráficas.
• Operaciones.
• Distancia y gráficas conexas.
• Caminos, paseos, trayectorias y ciclos.
• Gráficas bipartitas

2. Árboles

• Árboles y bosques.
• Árboles generadores.

3. Conexidad

• Vértices de corte y puentes.
• Conexidad puntual y lineal.
• Bloques.

4. Recorridos eulerianos y hamiltonianos.

• Gráficas eulerianas.
• Gráficas hamiltonianas.
• Aplicaciones.

5. Apareamientos

• Apareamientos en gráficas.
• Teorema de Hall.
• El algoritmo húngaro.

6. Coloración y planaridad

• Coloración por vértices.
• Número cromático.
• Gráficas planas.
• Fórmula de Euler.
• Teorema de los 5 colores.

Bibliografía:

• Chartrand, G., Zhang P. A first course in graph theory, Dover Publications, 2012.

• Chartrand G. Introductory graph theory, Dover Publications, 1985.

• Bondy, J.A., Murty, U.S., Graph Theory with Applications, Macmillan, 1976.

• Harary, F., Graph Theory, Reading, Addison-Wesley Publishing Company, 1969.

Forma de evaluación: Se dejarán al rededor de 6 tareas-examen durante el curso. La calificación final es el promedio de todas ellas. Se puede reponer exactamente una tarea-examen.

Libro de consulta: Graph Theory with Applications, Bondy & Murty.