Grafy II.

Michal Roch
Mind Map by Michal Roch, updated more than 1 year ago
Michal Roch
Created by Michal Roch about 4 years ago
47
0

Description

Grafy 2
Tags

Resource summary

Grafy II.
1 Stromy
1.1 Definice
1.1.1 Spojitý graf bez cyklů
1.1.2 Přidání nové hrany bez uzlu způsobí vznik cyklu
1.1.3 Odebrání libovolné hrany zpusobí vznik izolovaného uzlu
1.1.4 Obsahuje právě |V|-1 hran
1.1.5 Libovolné dva uzly jsou spojeny právě jednou cestou
1.2 Orientovaný
1.2.1 List je uzel se stupněm 1
1.2.2 Kořen může být kterýkoli uzel
1.3 Neorientovaný
1.3.1 List je uzel bez odchozích hran
1.3.2 Kořen je uzel bez příchozích hran
2 Reprezentace
2.1 Matice sousednosti
2.1.1 Čtvercová matice VxV
2.1.2 Dimenze jsou uzly grafu
2.1.2.1 1 pokud jsou spojeny hranou
2.1.2.2 0 pokud nejsou spojeny hranou
2.1.3 Orientovaný graf
2.1.3.1 1 pokud i->j
2.1.3.2 0 v ostatních případech
2.1.4 Rychlost
2.1.4.1 Náročné na pamět
2.1.4.2 Pomalé přidávání a odebírání uzlů
2.1.4.3 Rychlé přidávání a odebírání hran
2.1.4.4 Rychlé dotazy na sousednost a stupeň
2.2 Laplaceova matice
2.2.1 Čtvercová matice VxV
2.2.2 Dimenze jsou uzly grafu
2.2.2.1 Na diagonále stupeň grafu
2.2.2.2 -1 pokud jsou spojeny hranou
2.2.2.3 0 pokud nejsou spojeny hranou
2.3 Matice vzdáleností
2.3.1 Čtvercová matice VxV
2.3.2 Dimenze jsou uzly grafu
2.3.2.1 Váha hrany pokud jsou spojeny
2.3.2.2 0 pokud nejsou spojeny hranou
2.4 Matice incidence
2.4.1 Matice VxE
2.4.2 Dimenze jsou uzly (řádek) a hrany (sloupec) grafu
2.4.2.1 1 pokud hrana spojuje uzel
2.4.2.2 0 pokud hrana nespojuje uzel
2.4.2.3 Každý sloupec obsahuje právě dvě 1
2.4.3 Hodnost matice je menší než počet uzlů
2.4.4 Orientovaný graf
2.4.4.1 1 pro odchozí uzel
2.4.4.2 -1 pro příchozí uzel
2.4.4.3 0 v ostatních případech
2.4.5 Rychlost
2.4.5.1 Nejnáročnější na paměť
2.4.5.2 Pomalé přidávání nebo mazání uzlů a hran
2.5 Matice dosažitelnosti
2.5.1 Čtvercová matice VxV
2.5.2 Dimenze jsou uzly grafu
2.5.2.1 1 pokud existuje cesta z i do j
2.5.2.2 0 v ostatních případech
2.6 Adjacency list
2.6.1 Pole jednosměrných seznamů
2.6.1.1 Může být i hash list nebo hash table
2.6.2 Velikost pole je V
2.6.3 Každý uzel udržuje (uspořádaný / neuspořádaný) seznam sousedů
2.6.4 Rychlost
2.6.4.1 Malé nároky na paměť
2.6.4.2 Rychlé přidání a odebrání uzlu nebo hrany
2.6.4.3 Pomalé dotazy na sousednost
3 DAG
3.1 Directed Acyclic Graph
3.2 Orientovaný graf bez cyklů
3.3 Není stromem - mezi dvěma uzly může existovat více cest
4 Prohledávání
4.1 DFS
4.1.1 Zásobníkem
4.1.1.1 Přidej potomky
4.1.1.2 Pop na vrchol zásobníku
4.1.1.3 Mark as visited
4.1.2 Rekurzí
4.1.2.1 FRESH
4.1.2.1.1 Dosud nenavštívený
4.1.2.1.2 Stromová hrana
4.1.2.2 OPEN
4.1.2.2.1 Po zavolání rekurze
4.1.2.2.2 Zpětná hrana
4.1.2.2.2.1 Znamená cyklus
4.1.2.3 CLOSED
4.1.2.3.1 Při ukončení rekurze
4.1.2.3.1.1 Až po uzavření všech potomků
4.1.2.3.2 Dopředná nebo příčná hrana
4.1.2.3.2.1 Značí že graf není strom
4.1.3 Použití
4.1.3.1 Topologické uspořádání
4.1.3.2 Spojitost grafu
4.1.3.3 Hledání komponent grafu
4.1.3.4 Transformace grafu do orientovaného lesa
4.2 BFS
4.2.1 Frontou
4.2.1.1 FRESH
4.2.1.1.1 Dosud nenavštívený
4.2.1.2 OPEN
4.2.1.2.1 Při vyjmutí z fronty
4.2.1.3 CLOSED
4.2.1.3.1 Po přidání všech potomků do fronty
4.2.1.3.2 Uzavřen dříve než všichni jeho potomci
5 Topologické uspořádání
5.1 Generuje se pomocí DFS
5.1.1 V okamžiku uzavírání uzlu přidej na začátek seznamu
5.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)
5.3 Lze pouze pro acyklické grafy
5.4 Vhodné pro počítání minimální a maximální vzdálenosti uzlů
Show full summary Hide full summary

Similar

Project Communications Management
farzanajeffri
Common Technology Terms
Julio Aldine Branch-HCPL
Computing
Kwame Oteng-Adusei
Abstraction
Shannon Anderson-Rush
Network Protocols
Shannon Anderson-Rush
Introduction to the Internet
Shannon Anderson-Rush
RESTful Web Services with Express Framework and mongoose.
Angel Martínez Rodriguez
Web Designing & Development Full Tutorial
Nandkishor Dhekane
HTTPS explained with Carrier Pigeons
Shannon Anderson-Rush
Database design
linneamd