Grafy III.

Grafy III.

Určení minimální kostry
1. Jarník-Prim
  1. Algoritmus
    1. Přidej všechny uzly do fronty a nastav jim nekonečnou vzdálenost od podstromu
    2. Kořen má vzdálenost nula a NIL předchůdce
    3. Dokud fronta není prázdná
      1. Vyber nejbližší uzel a vyjmi ho z fronty
      2. Pro všechny jeho sousedy zkontroluj a případně nastav novou minimální vzdálenost a nového předchůdce
    4. Vypiš kostru po předchůdcích pro každý uzel
  2. Vlastnosti
    1. Maximálně |V(G)| kroků
    2. Výsledkem je strom protože se vždy přidávají jen listy. Navíc má právě |V(G)| uzlů = jedná se o minimální kostru
    3. Složitost O(n^2 + m)
    4. S Fibonacciho haldou lze až O(m + log(n)n)
  3. Popis
    1. Buduje podstrom od náhodného kořene
    2. Rozšířuje podstrom přidáváním uzlů, které mají k aktuálnímu podstormu nejkratší vzdálenost
2. Kruskal ("greedy")
  1. Popis
    1. Každý uzel je podstromem
    2. Prochází hrany uspořádané podle vah a rozšiřuje podstromy aniž by vytvářel cykly
    3. Hrany které vytváří cyklus přeskakuje
  2. Algoritmus
    1. Uspořádej hrany v rostoucí posloupnosti podle vah
    2. Projdi každou hranu v posloupnosti
    3. Pokud počáteční a koncový uzel není součástí stejného podstromu, přidej hranu a spoj oba podstromy
  3. Vlastnosti
    1. Právě |E(G)| iterací
      1. Může být zastaven dříve zařážkou po přidání |V(G)| - 1 hran
    2. Union-find problem
      1. Algoritmus používá dotaz na náležitost uzlu podstormu (FIND) a sjednocení podstromů (UNION)
      2. Prosté řešení
        Každý podstrom je spojový seznam
        Každý prvek obsahuje také odkaz na první prvek (reprezentant)
        O(FIND) = 1
        O(UNION) = n
        Nutno spojit seznamy
        Pro každý uzel připojovaného seznamu přepsat reprezentanta
        Lze vylepšit připojováním kratšiho ze seznamů - nutné udržovat délku seznamu u reprezentanta
        O(|E(G)|.log|V(G)| + |V(G)|^2)
      3. Vylepšená reprezentace
        Les kořenových stromů
        Každý prvek obsahuje jen odkaz na rodiče, kořen je reprezentant a sám sobě rodičem
        O(UNION) = 1
        Připojení rodiče jako potomka
        O(FIND) = n
        Vylepšíme heuristikami
        Zkracujeme cestu - při FIND přepojíme rodiče o úroveň výš - zkracujeme hloubku
        Vyvžujeme hodnost - při UNION připojíme podstrom s menším počtem uzlů (na začátku hodnost 0, při spojení +1)
        O(|E(G)|.log|V(G)|)
3. Borůvka
  1. Popis
    1. Rozdělí graf do komponent a v cyklech přidává každé komponentě hranu s nejnižší vahou
  2. Algoritmus
    1. Vytvoř K který obsahuje všechny uzly bez hran
      1. Graf K obsahuje právě E(G) komponent
    2. Dokud K obsahuje alespoň dvě komponenty
    3. Pro každou komponentu přidej hranu s nejnižší vahou
      1. Rozpad lesa na komponenty pomocí DFS
      2. Každý uzel má přiřazené číslo komponenty
      3. Pro každou hranu zjistíme, do kterých komponent patří
      4. Pro každou komponentu uložíme minimální hranu
      5. Po projítí všech hran ke každé komponentě přidáme novou minimální hranu
  3. Vlastnosti
    1. Po k iteracích všechny komponenty grafu mají alespoň 2^k uzlů
    2. Složitost O(|E(G)|.log|V(G)|)
Určení komponent grafu
1. Kosaraju-Sharir
  1. Popis
    1. Hledání silných komponent grafu
    2. Využívá rekurzivní DFS a transponovaného grafu k nalezení uzavřených komponent
  2. Algoritmus
    1. Přes DFS projdi celý graf
    2. V okamžiku uzavření uzel přidej do zásobníku
    3. Jakmile zásobník obsahuje všechny vrcholy (všechny uzly jsou closed)
    4. Obrať orientaci všech hran - vytvoř transponovaný graf
    5. Dokud zásobník není prázdný
      1. Vyjmi uzel
      2. Pokud je unvisited zavolej DFS nad transponovaným grafem
      3. Navštívené uzly v DFS tvoří komponentu
  3. Vlastnosti
    1. Adjacency matrix - max složitost O(|V|^2)
    2. DFS dvakrát nad celým grafem
    3. Adjacency list - průměrná složitost o(|V|+|E|)
2. Tarjan
  1. Popis
    1. Používá upravenou verzi DFS a počítá index prvků
    2. Komponentu uzavírá pokud ví, že z uzlu není dosažitelný prvek s nižším indexem
    3. Proto stačí jen jeden průchod grafem
    4. Při návratu z rekurze kontroluje, jestli index potomka je nižší než index rodiče a pamatuje si nejnižší dosažitelný index
  2. Algoritmus
    1. Zavolej DFS na všechny neobjevené uzly
    2. Při navštívení nového uzlu přiřaď uzlu index, přidej ho do zásobníku a zvyš počítadlo indexu o 1
    3. Před uzavřením uzlu zkontroluj, jestli jeho u.minindex == u.index
      1. Pokud ano, vyprázdňuj zásobník dokud nenarazíš na kořen (u) jako novou komponentu do seznamu komponent
      2. Tj. jestli jsme v kořenu komponenty
    4. DFS strom se dále nevětví => zkontrolujeme minimální dosažitelný prvek
      1. Tj. po návratu z rekurze
      2. nebo při odhalení visited potomka, který ještě není součástí uzavřené komponenty
        Pokud už je v uzavřené komponentě, je dosažitelný jen jednosměrně a nemá cenu ho řešit
      3. Přiřadíme u.minindex = min(u.index, s.minindex) kde s je potomek
  3. Vlastnosti
    1. Složitost stejná jako Kosaraju-Sharir
    2. Ale jen jeden průchod grafem - je rychlejší
Speciální tahy v grafu
1. Eulerův tah
  1. Tah, který projde všechny uzly a hrany grafu, a každou hranu navštíví právě jednou
  2. Podmínky
    1. Graf je souvislý
    2. Má právě 0 vrcholů lichého stupně
      1. tzv. Eulerian Tour
      2. Pokud Eulerův tah končí a začíná ve stejném uzlu
    3. Nebo má právě 2 vrcholy lichého stupně
      1. Pokud Eulerův tah končí a začíná v různých uzlech
  3. Jak nalézt Eulerův tah
    1. Popis
      1. Začíná se v uzlu lichého stupně pokud existuje, jinak libovolně
      2. Je rekurzivní
      3. Vhodné nejprve otestovat stupně uzlů a souvislost přes DFS
    2. Algoritmus
      1. Pro každého potomka uzlu
        Smaž hranu edge(v,u)
        Přidej do zásobníku hranu edge(v,u)
        Zavolej rekurzi na potomka (u)
      2. Rekurze se vrací pokud už neexistuje potomek (všechny hrany smazány)
    3. Vlastnosti
      1. Jeden průchod grafem
      2. Adjacency list - průměrná složitost o(|V|+|E|)
      3. Adjacency matrix - maximální složitost O(|V|^2)
2. Hamiltonovská cesta
  1. Cesta, která navštíví každý uzel právě jednou
    1. Nemusí projít všechny hrany
  2. NPC problém

Next up

Description

Resource summary

Similar

	Created by Michal Roch about 8 years ago