Asignación 2: Blogs - Wikis - Mensajes de video

Módulo 6 – Semana 2
Asignación 2: Blogs – Wikis – Mensajes de video

Antonio Marcos Medina Martínez

UPC – Lima – Perú

Seleccione un blog, wiki, o mensaje de vídeo y elija una idea relacionada con el contenido que desarrolló en el Módulo 5.

Para la presente asignación he decidido presenter un Blog. La dirección en la cual está mi blog es la siguiente:

http://www.amarcosmedinam.blogspot.com/

En el Módulo 5, para la semana 2, la asignación se denominaba Plan de Diseño; dicho plan desarrollaba la lección Árbol de expansion minima, las necesidades, los objetivos de aprendizaje, el contenido instruccional, las estrategias y recursos instruccionales y el tipo de evaluación.

Para la presente asignación voy a presentar algunas recomendaciones para el trabajo con árboles de expansion mínima.

ÁRBOL DE EXPANSIÓN MÍNIMA

En Matemática Discreta, una de las unidades se denomina árboles, recibe dicho nombre porque su estructura gráfica se asemeja a un árbol, por lo ramificado que es. Tiene muchas aplicaciones en contextos reales, por ejemplo en el tendido de líneas telefónicas, de redes eléctricas, de agua y desagüe, construcción de carreteras, etc. Entonces, dado un problema de contexto real, se trata de hacer un trazado que conecte a todos los vértices, en la cual la suma de los valores de las aristas (líneas que unen los vértices), sea mínima.  Para resolver estos problemas primero se les muestra un proceso manual con diversos algoritmos (Prim, Kruskal), luego se les muestra programas que lo resuelven (WinQsb). Por supuesto que el estudiante primero modela la situación para poder aplicar el programa.

Enseñar Matemática de por sí es un reto, más aún si el curso es en línea, el reto es que los estudiantes logren comprender el proceso de los dos algoritmos y para eso se les facilita documentos con la teoría, problemas resueltos, propuestos con respuestas, y se refuerza con la presentación de videos mostrando problemas resueltos; el otro reto, algo menor, es mostrarles la solución utilizando algún programa.

ÁRBOL DE EXPANSIÓN:

En el campo matemático de la teoría de grafos, un árbol de expansión T de un grafo conexo, no dirigido G es un árbol compuesto por todos los vértices y algunas (quizá todas) de las aristas de G. Informalmente, un árbol de expansión de G es una selección de aristas de G que forman un árbol que cubre todos los vértices. Esto es, cada vértice está en el árbol, pero no hay ciclos. Por otro lado, todos los puentes de G deben estar contenidos en T. Un árbol de expansión de un grafo conexo G puede ser también definido como el mayor conjunto de aristas de G que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices.
En ciertos campos de la teoría de grafos es útil encontrar el mínimo árbol de expansión de un grafo ponderado. También se han abordado otros problemas de optimización relacionados con los árboles de expansión, como el máximo árbol de expansión, el máximo árbol que cubre al menos k vértices, el mínimo árbol de expansión con k aristas por vértice como máximo (árbol de expansión de mínimo grado, MDST por sus siglas en inglés), el árbol de expansión con el máximo número de hojas (estrechamente relacionado con el problema del menos conjunto dominante y conexo), el árbol de expansión con el menor número de hojas (relacionado con el problema del camino hamiltoniano), el árbol de expansión de mínimo diámetro o el árbol de expansión de la mínima dilación.

ÁRBOL DE EXPANSIÓN MÍNIMA:

Dada una gráfica, su árbol mínimo generador (o árbol de peso mínimo o árbol mínimo de expansión) es un árbol que pasa por todos los vértices y que la suma de sus aristas es la de menor peso. La forma inmediata en que se nos puede ocurrir para encontrarlo es mediante una búsqueda exhaustiva, sin embargo, podemos encontrarlo más rápido.
De forma similar al problema de la distancia más corta, el árbol mínimo generador puede ser calculado mediante un enfoque ávido. La idea básica es empezar con el árbol vacío e irle agregando una arista a la vez. La arista que escogemos es la de menor costo que no forme un ciclo en nuestro árbol. Después de agregar V-1 aristas, el árbol que tenemos es el árbol mínimo generador. Con esta idea surgen dos algoritmos: Prim y Kruskal, cuya diferencia básica es la forma en que encontremos la arista que vamos a agregar.

Saludos

Antonio Marcos Medina Martínez
UPC – Lima – Perú