Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 5 vistas

    P-11 - Ramos Jose

    Cargado por

    Ya Mira
    El documento describe el algoritmo de Kruskal para encontrar el árbol de expansión mínimo en un grafo. Se presentan ejemplos de aplicación del algoritmo sobre un grafo con 10 vértices y 19 aristas, identificando el árbol mínimo y máximo.

    Copyright:

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

    P-11 - Ramos Jose

    Cargado por

    Ya Mira
    5 vistas3 páginas
    El documento describe el algoritmo de Kruskal para encontrar el árbol de expansión mínimo en un grafo. Se presentan ejemplos de aplicación del algoritmo sobre un grafo con 10 vértices y 19 aristas, identificando el árbol mínimo y máximo.

    Título original

    P-11_RAMOS JOSE

    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?

    El documento describe el algoritmo de Kruskal para encontrar el árbol de expansión mínimo en un grafo. Se presentan ejemplos de aplicación del algoritmo sobre un grafo con 10 vértices y 19 aristas, identificando el árbol mínimo y máximo.

    Copyright:

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

    P-11 - Ramos Jose

    Cargado por

    Ya Mira
    El documento describe el algoritmo de Kruskal para encontrar el árbol de expansión mínimo en un grafo. Se presentan ejemplos de aplicación del algoritmo sobre un grafo con 10 vértices y 19 aristas, identificando el árbol mínimo y máximo.

    Copyright:

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

    UNIVERSIDAD MAYOR DE SAN ANDRES ING.

    INDUSTRIAL
    INGENIERIA DE SIMULACION Y LABORATORIO IND-742

    NOMBRE: RAMOS YAMPASI JOSE FERNANDO

    DOCENTE:

    FECHA:
    ING. QUIROGA EDGAR

    16/03/2022

    PRACTICA Nº 11
    R
    R.U: 1766625
    Algoritmo de Kruskal
    Definición: Busca un subconjunto de aristas que, formando un árbol, incluyen todos los
    vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.

    1
    56 68
    222 3
    8 230
    89 99 108
    2
    140
    7 92
    179 86 4
    233
    9
    210 201 270 244
    77
    10 5
    100 6 312

    Vetices distancia
    1 2 68
    1 3 56
    2 3 230
    2 4 92
    2 5 233
    3 4 108
    3 7 99
    3 8 222 Debemos identificar entre los vértices las distancias
    4 5 244 mínimas, teniendo en cuenta que no podemos caer
    4 6 270 en un ciclo (cerrarnos)
    4 7 86
    5 6 312
    6 7 201
    6 10 100
    7 8 89
    7 9 179
    7 10 210
    8 9 140
    9 10 77

    1
    UNIVERSIDAD MAYOR DE SAN ANDRES ING. INDUSTRIAL
    INGENIERIA DE SIMULACION Y LABORATORIO IND-742

    ARBOL MINIMO

    1
    56 68
    222 3
    8 230
    89 99 108
    2
    140
    7 92
    179 86 4
    233
    9
    210 201 270 244
    77
    10 5
    100 6 312

    Nº Vetices distancia menor a mayor Vetices CICLOS


    1 1 2 68 56 1 3 -
    2 1 3 56 68 1 2 -
    3 2 3 230 77 9 10 -
    4 2 4 92 86 4 7 -
    5 2 5 233 89 7 8 -
    6 3 4 108 92 2 4 -
    7 3 7 99 99 Se cierra Ciclo 1-2-4-7-3
    8 3 8 222 100 6 10 -
    9 4 5 244 108 Se cierra Ciclo 1-2-4-3
    10 4 6 270 140 8 9 -
    11 4 7 86 179 Se cierra Ciclo 7-8-9
    12 5 6 312 201 Se cierra Ciclo 6-7-8-9-10
    13 6 7 201 210 Se cierra Ciclo 7-8-9-11
    14 6 10 100 222 Se cierra Ciclo 1-2-4-7-8-3
    15 7 8 89 230 Se cierra Ciclo 1-2-3
    16 7 9 179 233 2 5 -
    17 7 10 210 244 Se cierra Ciclo 2-4-5
    18 8 9 140 270 Se cierra Ciclo 4-7-8-9-10-6
    19 9 10 77 312 Se cierra Ciclo 2-4-7-8-9-10-6-5
    ARBOL MINIMO 941

    2
    UNIVERSIDAD MAYOR DE SAN ANDRES ING. INDUSTRIAL
    INGENIERIA DE SIMULACION Y LABORATORIO IND-742

    ARBOL MAXIMO

    1
    56 68
    222 3
    8 230
    89 99 108
    2
    140
    7 92
    179 86 4
    233
    9
    210 201 270 244
    77
    10 5
    100 6 312

    Nº Vetices distancia mayor a menor Vetices CICLOS


    1 1 2 68 270 4 6 -
    2 1 3 56 244 4 5 -
    3 2 3 230 233 2 5 -
    4 2 4 92 230 2 3 -
    5 2 5 233 222 3 8 -
    6 3 4 108 210 7 10 -
    7 3 7 99 201 6 7 -
    8 3 8 222 179 7 9 -
    9 4 5 244 140 Se cierra Ciclo 2-3-8-9-7-6-4-5
    10 4 6 270 108 Se cierra Ciclo 2-3-4-5
    11 4 7 86 100 Se cierra Ciclo 6-7-10
    12 5 6 312 99 Se cierra Ciclo 2-3-7-6-4-5
    13 6 7 201 92 Se cierra Ciclo 2-4-5
    14 6 10 100 89 Se cierra Ciclo 2-3-8-7-6-4-5
    15 7 8 89 86 Se cierra Ciclo 4-6-7
    16 7 9 179 77 Se cierra Ciclo 7-9-10
    17 7 10 210 68 1 2 -
    18 8 9 140 56 Se cierra Ciclo 1--3
    19 9 10 77 312 Se cierra Ciclo 4-5-6
    ARBOL MAXIMO 1857

    También podría gustarte