Grafy III.

Michal Roch
Mind Map by Michal Roch, updated more than 1 year ago
Michal Roch
Created by Michal Roch over 5 years ago
41
0

Description

Grafy 3

Resource summary

Grafy III.
  1. 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
          1. Kořen má vzdálenost nula a NIL předchůdce
            1. Dokud fronta není prázdná
              1. Vyber nejbližší uzel a vyjmi ho z fronty
                1. Pro všechny jeho sousedy zkontroluj a případně nastav novou minimální vzdálenost a nového předchůdce
                2. Vypiš kostru po předchůdcích pro každý uzel
                3. Vlastnosti
                  1. Maximálně |V(G)| kroků
                    1. 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
                      1. Složitost O(n^2 + m)
                        1. S Fibonacciho haldou lze až O(m + log(n)n)
                        2. Popis
                          1. Buduje podstrom od náhodného kořene
                            1. 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
                                1. Prochází hrany uspořádané podle vah a rozšiřuje podstromy aniž by vytvářel cykly
                                  1. Hrany které vytváří cyklus přeskakuje
                                  2. Algoritmus
                                    1. Uspořádej hrany v rostoucí posloupnosti podle vah
                                      1. Projdi každou hranu v posloupnosti
                                        1. Pokud počáteční a koncový uzel není součástí stejného podstromu, přidej hranu a spoj oba podstromy
                                        2. 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)
                                                1. Prosté řešení
                                                  1. Každý podstrom je spojový seznam
                                                    1. Každý prvek obsahuje také odkaz na první prvek (reprezentant)
                                                      1. O(FIND) = 1
                                                        1. O(UNION) = n
                                                          1. Nutno spojit seznamy
                                                            1. Pro každý uzel připojovaného seznamu přepsat reprezentanta
                                                              1. Lze vylepšit připojováním kratšiho ze seznamů - nutné udržovat délku seznamu u reprezentanta
                                                              2. O(|E(G)|.log|V(G)| + |V(G)|^2)
                                                              3. Vylepšená reprezentace
                                                                1. Les kořenových stromů
                                                                  1. Každý prvek obsahuje jen odkaz na rodiče, kořen je reprezentant a sám sobě rodičem
                                                                    1. O(UNION) = 1
                                                                      1. Připojení rodiče jako potomka
                                                                      2. O(FIND) = n
                                                                        1. Vylepšíme heuristikami
                                                                          1. Zkracujeme cestu - při FIND přepojíme rodiče o úroveň výš - zkracujeme hloubku
                                                                            1. 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)
                                                                            2. 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
                                                                                1. Pro každou komponentu přidej hranu s nejnižší vahou
                                                                                  1. Rozpad lesa na komponenty pomocí DFS
                                                                                    1. Každý uzel má přiřazené číslo komponenty
                                                                                      1. Pro každou hranu zjistíme, do kterých komponent patří
                                                                                        1. Pro každou komponentu uložíme minimální hranu
                                                                                          1. Po projítí všech hran ke každé komponentě přidáme novou minimální hranu
                                                                                        2. Vlastnosti
                                                                                          1. Po k iteracích všechny komponenty grafu mají alespoň 2^k uzlů
                                                                                            1. Složitost O(|E(G)|.log|V(G)|)
                                                                                        3. Určení komponent grafu
                                                                                          1. Kosaraju-Sharir
                                                                                            1. Popis
                                                                                              1. Hledání silných komponent grafu
                                                                                                1. Využívá rekurzivní DFS a transponovaného grafu k nalezení uzavřených komponent
                                                                                                2. Algoritmus
                                                                                                  1. Přes DFS projdi celý graf
                                                                                                    1. V okamžiku uzavření uzel přidej do zásobníku
                                                                                                      1. Jakmile zásobník obsahuje všechny vrcholy (všechny uzly jsou closed)
                                                                                                        1. Obrať orientaci všech hran - vytvoř transponovaný graf
                                                                                                          1. Dokud zásobník není prázdný
                                                                                                            1. Vyjmi uzel
                                                                                                              1. Pokud je unvisited zavolej DFS nad transponovaným grafem
                                                                                                                1. Navštívené uzly v DFS tvoří komponentu
                                                                                                              2. Vlastnosti
                                                                                                                1. Adjacency matrix - max složitost O(|V|^2)
                                                                                                                  1. DFS dvakrát nad celým grafem
                                                                                                                    1. 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ů
                                                                                                                        1. Komponentu uzavírá pokud ví, že z uzlu není dosažitelný prvek s nižším indexem
                                                                                                                          1. Proto stačí jen jeden průchod grafem
                                                                                                                            1. 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
                                                                                                                                1. 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
                                                                                                                                  1. 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
                                                                                                                                      1. Tj. jestli jsme v kořenu komponenty
                                                                                                                                      2. DFS strom se dále nevětví => zkontrolujeme minimální dosažitelný prvek
                                                                                                                                        1. Tj. po návratu z rekurze
                                                                                                                                          1. nebo při odhalení visited potomka, který ještě není součástí uzavřené komponenty
                                                                                                                                            1. Pokud už je v uzavřené komponentě, je dosažitelný jen jednosměrně a nemá cenu ho řešit
                                                                                                                                            2. Přiřadíme u.minindex = min(u.index, s.minindex) kde s je potomek
                                                                                                                                          2. Vlastnosti
                                                                                                                                            1. Složitost stejná jako Kosaraju-Sharir
                                                                                                                                              1. Ale jen jeden průchod grafem - je rychlejší
                                                                                                                                          3. 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
                                                                                                                                                1. Podmínky
                                                                                                                                                  1. Graf je souvislý
                                                                                                                                                    1. Má právě 0 vrcholů lichého stupně
                                                                                                                                                      1. tzv. Eulerian Tour
                                                                                                                                                        1. Pokud Eulerův tah končí a začíná ve stejném uzlu
                                                                                                                                                        2. 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ě
                                                                                                                                                              1. Je rekurzivní
                                                                                                                                                                1. Vhodné nejprve otestovat stupně uzlů a souvislost přes DFS
                                                                                                                                                                2. Algoritmus
                                                                                                                                                                  1. Pro každého potomka uzlu
                                                                                                                                                                    1. Smaž hranu edge(v,u)
                                                                                                                                                                      1. Přidej do zásobníku hranu edge(v,u)
                                                                                                                                                                        1. 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
                                                                                                                                                                            1. Adjacency list - průměrná složitost o(|V|+|E|)
                                                                                                                                                                              1. 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
                                                                                                                                                                            Show full summary Hide full summary

                                                                                                                                                                            Similar

                                                                                                                                                                            A level Computing Quiz
                                                                                                                                                                            Zacchaeus Snape
                                                                                                                                                                            Types and Components of Computer Systems
                                                                                                                                                                            Jess Peason
                                                                                                                                                                            Input Devices
                                                                                                                                                                            Jess Peason
                                                                                                                                                                            Output Devices
                                                                                                                                                                            Jess Peason
                                                                                                                                                                            Project Communications Management
                                                                                                                                                                            farzanajeffri
                                                                                                                                                                            Common Technology Terms
                                                                                                                                                                            Julio Aldine Branch-HCPL
                                                                                                                                                                            Network Protocols
                                                                                                                                                                            Shannon Anderson-Rush
                                                                                                                                                                            Computing
                                                                                                                                                                            Kwame Oteng-Adusei
                                                                                                                                                                            Abstraction
                                                                                                                                                                            Shannon Anderson-Rush
                                                                                                                                                                            HTTPS explained with Carrier Pigeons
                                                                                                                                                                            Shannon Anderson-Rush