Grafy II.

Grafy II.

Stromy
1. Definice
  1. Spojitý graf bez cyklů
  2. Přidání nové hrany bez uzlu způsobí vznik cyklu
  3. Odebrání libovolné hrany zpusobí vznik izolovaného uzlu
  4. Obsahuje právě |V|-1 hran
  5. Libovolné dva uzly jsou spojeny právě jednou cestou
2. Orientovaný
  1. List je uzel se stupněm 1
  2. Kořen může být kterýkoli uzel
3. Neorientovaný
  1. List je uzel bez odchozích hran
  2. Kořen je uzel bez příchozích hran
Reprezentace
1. Matice sousednosti
  1. Čtvercová matice VxV
  2. Dimenze jsou uzly grafu
    1. 1 pokud jsou spojeny hranou
    2. 0 pokud nejsou spojeny hranou
  3. Orientovaný graf
    1. 1 pokud i->j
    2. 0 v ostatních případech
  4. Rychlost
    1. Náročné na pamět
    2. Pomalé přidávání a odebírání uzlů
    3. Rychlé přidávání a odebírání hran
    4. Rychlé dotazy na sousednost a stupeň
2. Laplaceova matice
  1. Čtvercová matice VxV
  2. Dimenze jsou uzly grafu
    1. Na diagonále stupeň grafu
    2. -1 pokud jsou spojeny hranou
    3. 0 pokud nejsou spojeny hranou
3. Matice vzdáleností
  1. Čtvercová matice VxV
  2. Dimenze jsou uzly grafu
    1. Váha hrany pokud jsou spojeny
    2. 0 pokud nejsou spojeny hranou
4. Matice incidence
  1. Matice VxE
  2. Dimenze jsou uzly (řádek) a hrany (sloupec) grafu
    1. 1 pokud hrana spojuje uzel
    2. 0 pokud hrana nespojuje uzel
    3. Každý sloupec obsahuje právě dvě 1
  3. Hodnost matice je menší než počet uzlů
  4. Orientovaný graf
    1. 1 pro odchozí uzel
    2. -1 pro příchozí uzel
    3. 0 v ostatních případech
  5. Rychlost
    1. Nejnáročnější na paměť
    2. Pomalé přidávání nebo mazání uzlů a hran
5. Matice dosažitelnosti
  1. Čtvercová matice VxV
  2. Dimenze jsou uzly grafu
    1. 1 pokud existuje cesta z i do j
    2. 0 v ostatních případech
6. Adjacency list
  1. Pole jednosměrných seznamů
    1. Může být i hash list nebo hash table
  2. Velikost pole je V
  3. Každý uzel udržuje (uspořádaný / neuspořádaný) seznam sousedů
  4. Rychlost
    1. Malé nároky na paměť
    2. Rychlé přidání a odebrání uzlu nebo hrany
    3. Pomalé dotazy na sousednost
DAG
1. Directed Acyclic Graph
2. Orientovaný graf bez cyklů
3. Není stromem - mezi dvěma uzly může existovat více cest
Prohledávání
1. DFS
  1. Zásobníkem
    1. Přidej potomky
    2. Pop na vrchol zásobníku
    3. Mark as visited
  2. Rekurzí
    1. FRESH
      1. Dosud nenavštívený
      2. Stromová hrana
    2. OPEN
      1. Po zavolání rekurze
      2. Zpětná hrana
        Znamená cyklus
    3. CLOSED
      1. Při ukončení rekurze
        Až po uzavření všech potomků
      2. Dopředná nebo příčná hrana
        Značí že graf není strom
  3. Použití
    1. Topologické uspořádání
    2. Spojitost grafu
    3. Hledání komponent grafu
    4. Transformace grafu do orientovaného lesa
2. BFS
  1. Frontou
    1. FRESH
      1. Dosud nenavštívený
    2. OPEN
      1. Při vyjmutí z fronty
    3. CLOSED
      1. Po přidání všech potomků do fronty
      2. Uzavřen dříve než všichni jeho potomci
Topologické uspořádání
1. Generuje se pomocí DFS
  1. V okamžiku uzavírání uzlu přidej na začátek seznamu
2. 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)
3. Lze pouze pro acyklické grafy
4. Vhodné pro počítání minimální a maximální vzdálenosti uzlů

Next up

Description

Resource summary

Similar

	Created by Michal Roch almost 9 years ago