Matemáticas (plan 1983) 2015-2

Optativas de los Niveles I, II, III y IV, Graficas y Juegos

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 entre 6 y 8 tareas-examen durante el curso. La calificación final es el promedio de todas ellas. En caso de obtener un promedio menor a 6, el alumno puede presentar un examen final.

TAREAS:

• Tarea 1: Se entrega el 9 de marzo.
• Tarea 2: Se entrega el 27 de marzo.
• Tarea 3: Se entrega el 23 de abril.
• Tarea 4: Se entrega el 18 de mayo.
• Tarea 5: Se entrega el 27 de mayo.

EXAMENES DE REPOSICIÓN: Se entrega el lunes 8 de junio.

EXAMEN FINAL: Se entrega el miércoles 10 de junio.