Grafy II.

Grafy II.

1. Stromy

   • Definice
     • Spojitý graf bez cyklů
     • Přidání nové hrany bez uzlu způsobí vznik cyklu
     • Odebrání libovolné hrany zpusobí vznik izolovaného uzlu
     • Obsahuje právě |V|-1 hran
     • Libovolné dva uzly jsou spojeny právě jednou cestou
   • Orientovaný
     • List je uzel se stupněm 1
     • Kořen může být kterýkoli uzel
   • Neorientovaný
     • List je uzel bez odchozích hran
     • Kořen je uzel bez příchozích hran

2. Reprezentace

   • Matice sousednosti
     • Čtvercová matice VxV
     • Dimenze jsou uzly grafu
       • 1 pokud jsou spojeny hranou
       • 0 pokud nejsou spojeny hranou
     • Orientovaný graf
       • 1 pokud i->j
       • 0 v ostatních případech
     • Rychlost
       • Náročné na pamět
       • Pomalé přidávání a odebírání uzlů
       • Rychlé přidávání a odebírání hran
       • Rychlé dotazy na sousednost a stupeň
   • Laplaceova matice
     • Čtvercová matice VxV
     • Dimenze jsou uzly grafu
       • Na diagonále stupeň grafu
       • -1 pokud jsou spojeny hranou
       • 0 pokud nejsou spojeny hranou
   • Matice vzdáleností
     • Čtvercová matice VxV
     • Dimenze jsou uzly grafu
       • Váha hrany pokud jsou spojeny
       • 0 pokud nejsou spojeny hranou
   • Matice incidence
     • Matice VxE
     • Dimenze jsou uzly (řádek) a hrany (sloupec) grafu
       • 1 pokud hrana spojuje uzel
       • 0 pokud hrana nespojuje uzel
       • Každý sloupec obsahuje právě dvě 1
     • Hodnost matice je menší než počet uzlů
     • Orientovaný graf
       • 1 pro odchozí uzel
       • -1 pro příchozí uzel
       • 0 v ostatních případech
     • Rychlost
       • Nejnáročnější na paměť
       • Pomalé přidávání nebo mazání uzlů a hran
   • Matice dosažitelnosti
     • Čtvercová matice VxV
     • Dimenze jsou uzly grafu
       • 1 pokud existuje cesta z i do j
       • 0 v ostatních případech
   • Adjacency list
     • Pole jednosměrných seznamů
       • Může být i hash list nebo hash table
     • Velikost pole je V
     • Každý uzel udržuje (uspořádaný / neuspořádaný) seznam sousedů
     • Rychlost
       • Malé nároky na paměť
       • Rychlé přidání a odebrání uzlu nebo hrany
       • Pomalé dotazy na sousednost

3. DAG

   • Directed Acyclic Graph
   • Orientovaný graf bez cyklů
   • Není stromem - mezi dvěma uzly může existovat více cest

4. Prohledávání

   • DFS
     • Zásobníkem
       • Přidej potomky
       • Pop na vrchol zásobníku
       • Mark as visited
     • Rekurzí
       • FRESH
         • Dosud nenavštívený
         • Stromová hrana
       • OPEN
         • Po zavolání rekurze
         • Zpětná hrana
           • Znamená cyklus
       • CLOSED
         • Při ukončení rekurze
           • Až po uzavření všech potomků
         • Dopředná nebo příčná hrana
           • Značí že graf není strom
     • Použití
       • Topologické uspořádání
       • Spojitost grafu
       • Hledání komponent grafu
       • Transformace grafu do orientovaného lesa
   • BFS
     • Frontou
       • FRESH
         • Dosud nenavštívený
       • OPEN
         • Při vyjmutí z fronty
       • CLOSED
         • Po přidání všech potomků do fronty
         • Uzavřen dříve než všichni jeho potomci

5. Topologické uspořádání

   • Generuje se pomocí DFS
     • V okamžiku uzavírání uzlu přidej na začátek seznamu
   • Očíslování a uspořádání uzlů takové, že x <= y kde x je vždy před y (existuje cesta z x do y)
   • Lze pouze pro acyklické grafy
   • Vhodné pro počítání minimální a maximální vzdálenosti uzlů