Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 36 vistas

    Abcdefg

    Cargado por

    Ivan Rodriguez
    El documento presenta el algoritmo de Kruskal para encontrar el árbol de expansión mínima de un grafo. Primero se define una estructura de grafo con vértices y aristas. Luego, se implementa un conjunto disjunto y el algoritmo de Kruskal, el cual ordena las aristas por peso creciente y las va agregando al árbol mínimo siempre que no formen un ciclo. Finalmente, se aplica sobre un grafo de prueba y se imprime el resultado.

    Copyright:

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

    Abcdefg

    Cargado por

    Ivan Rodriguez
    36 vistas4 páginas
    El documento presenta el algoritmo de Kruskal para encontrar el árbol de expansión mínima de un grafo. Primero se define una estructura de grafo con vértices y aristas. Luego, se implementa un conjunto disjunto y el algoritmo de Kruskal, el cual ordena las aristas por peso creciente y las va agregando al árbol mínimo siempre que no formen un ciclo. Finalmente, se aplica sobre un grafo de prueba y se imprime el resultado.

    Descripción original:

    abcdefghijkmnlopkrstuvyz

    Título original

    abcdefg

    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?

    El documento presenta el algoritmo de Kruskal para encontrar el árbol de expansión mínima de un grafo. Primero se define una estructura de grafo con vértices y aristas. Luego, se implementa un conjunto disjunto y el algoritmo de Kruskal, el cual ordena las aristas por peso creciente y las va agregando al árbol mínimo siempre que no formen un ciclo. Finalmente, se aplica sobre un grafo de prueba y se imprime el resultado.

    Copyright:

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

    Abcdefg

    Cargado por

    Ivan Rodriguez
    El documento presenta el algoritmo de Kruskal para encontrar el árbol de expansión mínima de un grafo. Primero se define una estructura de grafo con vértices y aristas. Luego, se implementa un conjunto disjunto y el algoritmo de Kruskal, el cual ordena las aristas por peso creciente y las va agregando al árbol mínimo siempre que no formen un ciclo. Finalmente, se aplica sobre un grafo de prueba y se imprime el resultado.

    Copyright:

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

    Pregunta 1y 2

    T(n) =14T(n-1) – 6T(n-2) + 100T(n-3)


    Condiciones iniciales: T(k) = 2k; para k de 1 a 3

    1. Reordenando los términos:

    T(n) -14T(n-1) + 6T(n-2) - 100T(n-3) = 0

    T(n)=8k3

    2. Obteniendo la ecuación característica:

    8x3 – 56x2 – 12x -100 = 0

    3. Resolviendo la ecuación característica:

    ( x - 7.04 ) ( x + 0.02) ( x + 0.02 ) = 0

    𝑟1= 7,04 𝑟2= -0,02 𝑟3= -0.02

    4. Generando la ecuación de recurrencia (con coeficientes c1, c2 y c3)

    (𝑛) = f(c1, c2, c3, n) = _________________________________________________

    5. Resolviendo de las condiciones iniciales

    𝑐1 = __________ 𝑐2 = __________ 𝑐3 = __________

    6. Ecuación explicita:

    𝑻(𝒏) = _____________________________________________________________

    7. Orden de complejidad de T(n)

    T(n) ∈ ( _______)
    T(n) = 22T(n – 1) – 181T(n – 2) + 660T(n – 3) – 900T(n – 4)
    Condiciones iniciales: T(k) = k2; para k de 1 a 4

    Calcular la ecuación explícita de T(n), para los valores iniciales determinados por usted.

    1. Reordenando los términos:

    T(n) - 22T(n – 1) +181T(n – 2) - 660T(n – 3) + 900T(n – 4) = 0

    T(n) = x4

    2. Obteniendo la ecuación característica:

    X4 – 22x3 +181x2 -660x +900 = 0

    3. Resolviendo la ecuación característica:

    ( x-6 )( x-6 )( x-5 )( x–5)=0

    𝑟1= 6 𝑟 2= 6 𝑟3= 5 𝑟 4= 5

    Pregunta 3

    int dd =21;
    int mm=6;
    int yy=96;
    int []ns = {813,
    …
    206};
    int []table = {
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
    };
    //21/07/96
    int resultado = 0 ;
    for(int i = 0; i < ns.length;i++){
    //System.out.print(ns[i] + " ");
    int h1 = (ns[i])%dd;
    int h2 = (ns[i])%mm;
    for(int j = 0 ; j < 5000;j++){
    resultado = (h1 - h2*dd*i + mm*i*i + yy*i*i*i )%yy;
    //System.out.print(resultado+ " ");

    if(table[resultado]==-1){
    table[resultado]= ns[i];
    break;
    }
    }
    //System.out.println("");
    }

    for(int h=0;h < table.length;h++){


    System.out.print( h+ " : ");
    System.out.println(
    (table[h]==1)?"":String.valueOf(table[h]));
    }

    Pregunta 4
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <set>

    using namespace std;

    struct Arista {
    int u;
    int v;
    int w;

    Arista(int u, int v, int w) : u(u), v(v), w(w) {}


    };

    struct Grafo {
    set<int> v;
    vector<Arista> e;
    };

    class ConjuntoDisjunto {
    vector<int> ds;
    public:
    ConjuntoDisjunto(int n) {
    for (int i = 0; i < n; ++i) {
    ds.push_back(-1);
    }
    }
    int find(int u) {
    if (ds[u] < 0) {
    return u;
    } else {
    return find(ds[u]);
    }
    }
    void unir(int u, int v) {
    int x = find(u);
    int y = find(v);
    ds[y] += ds[x];
    ds[x] = y;
    }
    void print() {
    for (int i : ds) {
    cout << i << ",";
    }
    cout << endl;
    }
    };

    bool compara(Arista a, Arista b) {


    return a.w < b.w;
    }

    Grafo kruskalMst(Grafo g) {
    Grafo a;
    ConjuntoDisjunto cd(g.v.size());
    sort(g.e.begin(), g.e.end(), compara);
    for (Arista e : g.e) {
    cout << "Probando: (" << e.u << ", " << e.v << ")\n";
    cd.print();
    if (cd.find(e.u) != cd.find(e.v)) {
    a.e.push_back(Arista(e.u, e.v, e.w));
    a.v.insert(e.u);
    a.v.insert(e.v);
    cd.unir(e.u, e.v);
    }
    }
    return a;
    }

    int main() {
    Grafo g;
    g.v.insert(0);
    g.v.insert(1);
    g.v.insert(2);
    g.v.insert(3);

    g.e.push_back(Arista(0, 1, 1));
    g.e.push_back(Arista(2, 3, 1));
    g.e.push_back(Arista(1, 2, 2));
    g.e.push_back(Arista(1, 3, 3));
    g.e.push_back(Arista(0, 2, 5));

    Grafo a = kruskalMst(g);

    int wtotal = 0;
    for (Arista e : a.e) {
    wtotal += e.w;
    cout << "(" << e.u << ", " << e.v << ")\n";
    }return 0;}

    También podría gustarte