Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 38 vistas

    Lectura 4 Árboles Expandidos

    Cargado por

    Facundo Aybar
    Este documento describe el problema del árbol de expansión mínima (MST, por sus siglas en inglés). Explica que dado un grafo con aristas que tienen pesos o costos asociados, el objetivo es encontrar un subárbol que incluya todos los vértices pero cuyo costo total sea mínimo. Presenta el algoritmo de Kruskal como un método para resolver este problema de forma eficiente.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Lectura 4 Árboles Expandidos

    Cargado por

    Facundo Aybar
    38 vistas5 páginas
    Este documento describe el problema del árbol de expansión mínima (MST, por sus siglas en inglés). Explica que dado un grafo con aristas que tienen pesos o costos asociados, el objetivo es encontrar un subárbol que incluya todos los vértices pero cuyo costo total sea mínimo. Presenta el algoritmo de Kruskal como un método para resolver este problema de forma eficiente.

    Título original

    Lectura 4 Árboles expandidos

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe el problema del árbol de expansión mínima (MST, por sus siglas en inglés). Explica que dado un grafo con aristas que tienen pesos o costos asociados, el objetivo es encontrar un subárbol que incluya todos los vértices pero cuyo costo total sea mínimo. Presenta el algoritmo de Kruskal como un método para resolver este problema de forma eficiente.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    38 vistas5 páginas

    Lectura 4 Árboles Expandidos

    Cargado por

    Facundo Aybar
    Este documento describe el problema del árbol de expansión mínima (MST, por sus siglas en inglés). Explica que dado un grafo con aristas que tienen pesos o costos asociados, el objetivo es encontrar un subárbol que incluya todos los vértices pero cuyo costo total sea mínimo. Presenta el algoritmo de Kruskal como un método para resolver este problema de forma eficiente.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 5

    Problema

    MST

    Matemática
    Discreta

    1
    Árbol expandido
    Supongamos que G = (V, E) es un grafo conexo y que T es un subconjunto de
    E tal que:
     (i) cada vértice de G pertenece a una arista en T;
     (ii) las aristas de T forman un árbol.

    Llamamos a T árbol expandido de G. En un grafo, puede haber distintos


    árboles expandidos. El gráfico siguiente indica con líneas más gruesas un
    ejemplo de árbol expandido dentro de un grafo.

    Figura 1: Árbol expandido

    b e
    d
    c

    f
    h
    g

    Fuente: elaboración propia.

    ¿Cómo encontrar un árbol expandido dentro de un grafo?


    Se elige un vértice del grafo G cualquiera. A partir de este vértice, que
    podemos llamar v, tenemos que agregarle una arista incidente en v. De esta
    manera se obtiene un árbol parcial. Ahora, hay que agregar otra arista
    incidente en el vértice v que no esté en el árbol parcial. Cada arista que
    añadimos no debe tener vértices incidentes ya utilizados. En el ejemplo
    dado, el agoritmo sería como sigue: se empieza por el vértice a, luego se
    elige el vértice b. El orden de los vértices elegidos quedaría: a, b, c, e, f, d, h
    y, por último, g. Las aristas utilizadas empiezan por ab, continúan por ac y
    terminan en la arista ae. A partir de allí, el orden de la aristas elegidas sería:
    cf, fd, fh, hg. En general, si hay n vértices, nosotros deberemos hacer
    n - 1 pasos, después de los cuales tendremos 1 + (n - 1) = n vértices y n - 1
    aristas.

    2
    Algoritmo de construcción de un árbol expandido:
    Inicio: cualquier vértice.
    Paso i: S es el conjunto de vértices tomado del grafo G para el árbol T. Se
    debe elegir una arista que tenga un extremo en S y el otro en el
    complemento de S. Si no existe una arista que tenga un extremo en S y el
    otro su complemento, entonces no existe un camino entre S y su
    complemento; por lo tanto, G es disconexo, lo cual contradice las hipótesis.
    Por consiguiente, siempre existe una arista disponible en cada etapa de la
    construcción.

    Problema MST

    Si a los grafos que hemos estudiado les agregamos otra característica: cada
    arista tiene un “peso”, entonces el problema de buscar un árbol expandido
    de menor peso se convierte en un problema que se aplica a muchas
    situaciones concretas, como la construcción de una red de gasoductos o la
    construcción de rutas que conceten diferentes ciudades, etcétera. Por
    ejemplo, en el problema de construcción de gasoductos, si bien para algunos
    pares de ciudades hay varias opciones de entrelasarlas, para otras es
    imposibles unirlas (cuestiones geográficas). Para esos pares de ciudades que
    hay varias opciones de unión esas uniones tienen distintos costos. Esos son
    factores a tener en cuenta.

    Este problema se formula así: dados un grafo G = (V, E) y una función costo
    en el conjunto de aristas, c(e), representa el costo de construir la arista e.
    Diremos que (G, c) es un grafo con “pesos” y que c es la función de pesos (o
    costos). Y el objetivo es construir un árbol de “mínimo” peso, es decir, que
    el costo total del árbol sea mínimo. Así, c(T) = ∑ c(e) es el costo total del árbol
    T.

    Puedes encontrar este tema, en la bibliografía obligatoria de la materia,


    como “el problema del conector”, o bien en otros libros, con la
    denominación MST por sus siglas de la expresión en inglés Minimum
    Spanning Tree.

    Dado que los valores de c son enteros positivos, claramente el problema


    MST debe tener solución, puesto que hay solo un número finito de árboles
    expandidos T para G, y cada uno de ellos da un valor entero positivo c(T). En
    otras palabras, podemos encontrar un árbol que asuma el valor mínimo,
    pero la pregunta es: ¿será el único?, evidentemente puede haber más de
    uno con ese costo.
    Si al algoritmo que explicamos anteriormente, para la construcción de un
    árbol expandido T dentro de un grafo G, le agregramos que la elección de la

    3
    lista sea siempre la de menor peso (costo), entonces tenemos un algoritmo
    simple para obtener un MST llamado estrategia greedy (si hay varias aristas
    con la misma propiedad, se selecciona una de ellas).

    Figura 2: Título : MST

    u
    6 u 2
    u 8 4 u
    z u u r
    2 5
    u u u
    u u
    7 6
    3 u 5
    u u
    u
    u u
    y 7 xu
    y u uu
    Fuente: elaboración propia.
    u u
    Hagamos un ejemplo para la figura 2:
    Vértice de inicio: u
    Arístas:ur,ux,uy,yz.

    Vértice de inicio: y
    Arístas : yz, yu, ur, ux

    El algoritmo greedy funciona muy bien para el problema MST.

    “El algoritmo de Kruskal es el más conocido para hallar el árbol de


    Expansión Mínima (MST) que usa técnicas algorítmicas greedy”

    ¿Cómo surgen estas técnicas? Una buena idea acerca de ello puede ser
    encontrada en la biografía de Joseph Kruskal. Era un matemático que
    trabajaba en la compañía telefónica Bell-Labs y diseñó un algoritmo que se
    puede aplicar al modelo de distribución de las líneas telefónicas. También es
    posible emplearlo en el diseño de la redes de transporte, de
    telecomunicaciones, en el análisis de imágenes, etcétera. Hay otros tipos de
    algoritmos y aplicaciones distintas muy importantes. Puedes buscar en la
    bibliografía el desarrollo de estos algoritmos.

    4
    Referencias
    Biggs, N. L. (1993). Discrete Mathematics. Reino Unido: Oxford University
    Press.

    Espinosa Armenta, R. (2010). Matemática Discreta (pp. 52-97). México:


    Alfaomega.

    Grimaldi, R. P. (1998). Matemáticas discreta y combinatoria: Una


    Introducción con aplicaciones. México: Pearson Educación.

    Pickover, C. A. (2012). El libro de las Matemáticas. Holanda: Librero.

    También podría gustarte