Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 185 vistas

    Arboles de Expansion

    Cargado por

    adrian torres
    Un árbol de expansión es un subgrafo que conecta todos los vértices de un grafo sin ciclos. Un árbol de expansión mínima es un árbol de expansión que tiene la suma mínima de pesos en sus aristas. Algoritmos como Dijkstra, Prim y Kruskal pueden encontrar el árbol de expansión mínima de un grafo conexo no dirigido con pesos en sus aristas.

    Copyright:

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

    Arboles de Expansion

    Cargado por

    adrian torres
    185 vistas1 página
    Un árbol de expansión es un subgrafo que conecta todos los vértices de un grafo sin ciclos. Un árbol de expansión mínima es un árbol de expansión que tiene la suma mínima de pesos en sus aristas. Algoritmos como Dijkstra, Prim y Kruskal pueden encontrar el árbol de expansión mínima de un grafo conexo no dirigido con pesos en sus aristas.

    Título original

    Arboles de expansion.docx

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Un árbol de expansión es un subgrafo que conecta todos los vértices de un grafo sin ciclos. Un árbol de expansión mínima es un árbol de expansión que tiene la suma mínima de pesos en sus aristas. Algoritmos como Dijkstra, Prim y Kruskal pueden encontrar el árbol de expansión mínima de un grafo conexo no dirigido con pesos en sus aristas.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    185 vistas1 página

    Arboles de Expansion

    Cargado por

    adrian torres
    Un árbol de expansión es un subgrafo que conecta todos los vértices de un grafo sin ciclos. Un árbol de expansión mínima es un árbol de expansión que tiene la suma mínima de pesos en sus aristas. Algoritmos como Dijkstra, Prim y Kruskal pueden encontrar el árbol de expansión mínima de un grafo conexo no dirigido con pesos en sus aristas.

    Copyright:

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

    Árboles de Expansión

    Dado un grafo conexo, no dirigido G. Un árbol de expansión es un árbol compuesto por todos los vértices y
    algunas (posiblemente todas) de las aristas de G. Al ser creado un árbol no existirán ciclos, además debe existir
    una ruta entre cada par de vértices.

    Árbol de Expansión Mínima


    Dado un grafo conexo, no dirigido y con pesos en las aristas, un árbol de expansión mínima es un árbol
    compuesto por todos los vértices y cuya suma de sus aristas es la de menor peso.

    El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos, los más
    conocidos son Dijkstra, Prim y Kruskal.

    También podría gustarte