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ů

## Tranzitivní uzávěr

Definice

Tranzitivní uzávěr orientovaného grafu je orientovaný graf s původními vrcholy a platí, že existuje hrana z uzlu u do uzlu v právě tehdy, když v původním orientovaném grafu existuje libovolná orientovaná cesta z uzlu u do uzlu v.

Obrázok: Tranzitivní uzávěr grafu (zdroj: http://zorro.fme.vutbr.cz/graphs/foil36.html)

Poznámka

Platí, že matice dosažitelnosti v grafu = matice sousednosti tranzitivního uzávěru grafu .

Algoritmus

Z každého vrcholu vypustit DFS (Depth-first search - prohledávání do hloubky), do společné matice zaznamenávat dosažené vrcholy (řádek odpovídá vrcholu, sloupce vrcholům, které jsou z něho dosažitelné) - složitost .

Warshallův algoritmus

Iterativní konstrukce matice dosažitelnosti, postupně počítá matice , kde , pokud mezi vrcholy a existuje cesta, jejíž všechny vnitřní vrcholy jsou mezi vrcholy .

Z matice lze spočítat matici - buď vede mezi vrcholy cesta, která nepoužije vrchol , nebo taková, která ho použije - v tom případě ale musí vést cesty mezi vrcholy a , které používají pouze vrcholy , jejich spojením je cesta mezi vrcholy

Matice je matice incidence původního grafu.

Pseudokód (vstup: I - matice incidence, ):

    Procedure Warshall(I)
    W:= I;
    for k:=1 to n
    begin
    for i:=1 to n
    begin
    for j:=1 to n

    end
    end
    return W;

Složitost algoritmu je jasně (potřebuje bitových operací), což může být lepší pro grafy s hodně hranami (počet hran se blíží ), než složitost ( )

TODO: ještě něco?