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:
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ínezUPC – Lima – Perú
