Árboles y algoritmos

Objetivo

Repasar conceptos básicos y mencionar algunas aplicaciones de la teoría de gráficas. Introducir los árboles, trabajar algunos ejemplos y conocer algoritmos para determinar árboles recubridores de peso máximo y peso mínimo asociados a gráficas conexas sin lazos.

Motivación

Presentamos un vídeo con información histórica que hace énfasis en los problemas reales que dieron lugar al nacimiento de la teoría de gráficas y en aplicaciones concretas que impulsaron su desarrollo inicial.

Inicio

Para iniciar recordamos conceptos básicos de la teoría de gráficas, los cuales explicamos y comentamos de manera sencilla. A continuación invitamos a realizar una actividad de manipulación manual de una digráfica y un de una gráfica. Concluimos mencionando aplicaciones genéricas de esta teoría y la importancia de los árboles dentro de la misma.

Desarrollo

Consta de tres secciones:

• Árboles. Definimos esta clase particular de gráfica, hablamos de sus propiedades escenciales e invitamos a observar y practicar con un algoritmo de búsqueda binaria.
• Árboles con raíz. Definimos este tipo de árboles, presentamos algunos ejemplos y propiedades.
• Árboles recubridores. Introducimos las gráfica ponderados y posteriormente los árboles recubridores como herramientas de optimización. Incluimos una escena para practicar algoritmos de generación de árboles recubridores de peso mínimo y máximo.

Cierre

Presentamos vídeos, con explicaciones muy claras, sobre el algoritmo de Kruskal y el algoritmo de Prim.

Créditos

Escena original

Adaptación