Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Minimální kostra grafu

Úkolem v této úloze je najít kostru (acyklický souvislý podgraf) grafu s celkovou minimální vahou hran. Vždy platí . Bez újmy na obecnosti lze předpokládat, že ohodnocení hran jsou nezáporná (lze ke všem přičíst konstantu a výsledek se nezmění).

Algoritmus (Borůvkův / Kruskalův algoritmus)

    Borůvka( V - vrcholy, E - hrany ){

    S = setříděné hrany podle jejich váhy;
    přiřaď vrcholům čísla komponent souvislosti;
    F = {};     // tj. (V,F) je "les", kde každý vrchol je
    // jedna komponenta souvislosti

    while( S není prázdná ){
    vyber z S další hranu (x,y);
    if ( číslo komponenty x != číslo komponenty y ){
    F += (x,y);
    slij komponenty příslušné k x a y;
    }
    }
    return ( (V,F) jako minimální kostru (v,E) );
    }

Celková složitost je při použití spojových seznamů: Setřídění hran podle váhy , nalezení čísla komponenty konstantní čas, max. počet přečíslování komponent při slévání (přečíslovávám-li vždy menší ze slévaných komponent) pro 1 vrchol je , tj. celkem .

Algoritmus je korektní - vždy nalezne kostru, protože přidá právě hran a nevytvoří nikdy cyklus. Minimalita kostry se dokáže sporem - mám-li vrácenou algoritmem a nějakou min. kostru, tak pokud je , najdu hranu , vezmu kostru (a ). Pokud mám nalezené takové, že , jsou i minimální, jinak taky nebylo minimální, protože je menší.

Algoritmus (Jarníkův / Primův algoritmus )

    Jarník( V - vrcholy, E - hrany, r - startovní vrchol ){

    Q = V;  // množina používaných vrcholů, dosud nepřipojených
    // ke kostře
    F = {}; // vznikající kostra, v každém okamžiku
    // je strom

    inicializace - nastav klíč(v) na nekonečno
    pro všechny vrcholy;
    klíč(r) = 0;
    soused(r) = NULL;

    while( Q je neprázdná ){
    vyber u, prvek s nejmenším klíčem z Q;
    F += ( soused(u),u );
    foreach( vrchol v, z u do v vede hrana ){
    if ( v je v Q a klíč(v) > w(u,v) ){
    klíč(v) = w(u,v);
    soused(v) = u;
    }
    }
    }
    return ( (V,F) jako min. kostru (V,E) );
    }

Složitost algoritmu je , pokud je reprezentováno jako bin. halda - nejvýše -krát upravuji klíč nějakého vrcholu, což má v haldě složitost , výběr minima max. -krát a inicializace jen .

Vytvořený graf je kostra, protože nikdy nevzniká cyklus (připojuji právě vrcholy z , která je na konci prázdná). Důkaz minimality podle konstrukce - najdu první hranu v min. kostře , která není ve výsledku alg. , pak najdu , t.ž. je kostra, z algoritmu je . Vezmu , vím, že a tedy je min. kostra, iterací tohoto postupně dostanu, že je min. kostra.