User Tools
Site Tools
teorie_grafu
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
teorie_grafu [2017/01/12 21:35] efox |
teorie_grafu [2017/09/21 16:31] (current) efox |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| + | <WRAP center round tip 60%> | ||
| + | základní pojmy, klasifikace, | ||
| + | </ | ||
| + | |||
| ====== graf ====== | ====== graf ====== | ||
| * http:// | * http:// | ||
| * = grafické vyjádření vztahů mezi objekty | * = grafické vyjádření vztahů mezi objekty | ||
| + | * = dvojice disjunktních množin uzlů (vrcholů, vertex-vertices) a hran (edge-edges), | ||
| * {{:: | * {{:: | ||
| * **incidence** = místu vstupu nebo výstupu hrany, vztah hrany s uzlem | * **incidence** = místu vstupu nebo výstupu hrany, vztah hrany s uzlem | ||
| Line 13: | Line 18: | ||
| * pro orientovaný graf | * pro orientovaný graf | ||
| * H -> U × U (kartézský součin - množina všech uspořádaných dvojic prvků z množiny U) | * H -> U × U (kartézský součin - množina všech uspořádaných dvojic prvků z množiny U) | ||
| + | |||
| + | {{ :: | ||
| * **kostra grafu** | * **kostra grafu** | ||
| * libovolný podgraf spojující hranami všechny vrcholy původního grafu | * libovolný podgraf spojující hranami všechny vrcholy původního grafu | ||
| Line 72: | Line 79: | ||
| ===== tah ===== | ===== tah ===== | ||
| * sled, kde není žádná hrana víc než jedenkrát | * sled, kde není žádná hrana víc než jedenkrát | ||
| + | * sled, kde se neopakují hrany | ||
| ===== uzavřený tah ===== | ===== uzavřený tah ===== | ||
| * končí tam kde začal. tak jak my. | * končí tam kde začal. tak jak my. | ||
| ===== cesta ===== | ===== cesta ===== | ||
| - | * je sled, ve kterém se neopakují vrcholy, tedy každý vrchol se v cestě objevuje nejvýše jednou. Existuje-li mezi dvěma vrcholy sled v grafu, existuje mezi nimi i cesta | + | * je sled, ve kterém se neopakují vrcholy |
| + | * tedy každý vrchol se v cestě objevuje nejvýše jednou. Existuje-li mezi dvěma vrcholy sled v grafu, existuje mezi nimi i cesta | ||
| ===== kružnice ===== | ===== kružnice ===== | ||
| * každá uzavřená cesta | * každá uzavřená cesta | ||
| Line 92: | Line 101: | ||
| * počet hran mezi dvěma sousedními uzly | * počet hran mezi dvěma sousedními uzly | ||
| * vím | * vím | ||
| + | * {{:: | ||
| ===== datovými strukturami ===== | ===== datovými strukturami ===== | ||
| ===== matematicky ===== | ===== matematicky ===== | ||
| Line 99: | Line 109: | ||
| * matice sousednosti má UZLY a UZLY v X i Y | * matice sousednosti má UZLY a UZLY v X i Y | ||
| * tohle to má nahoře HRANY a vlevo UZLY | * tohle to má nahoře HRANY a vlevo UZLY | ||
| + | * {{:: | ||
| * **matice dosažitelnosti** | * **matice dosažitelnosti** | ||
| * je jenom dole pod diagonálou | * je jenom dole pod diagonálou | ||
| Line 147: | Line 158: | ||
| ==== úlohy ==== | ==== úlohy ==== | ||
| - | * hledání trasy z A do B | + | |
| * přímo nebo přes libovolný počet průjezdních bodů | * přímo nebo přes libovolný počet průjezdních bodů | ||
| * výsledkem může být grafický element optimální trasy, ale i podrobný itinerář, přes které ulice nebo čísla silnic se do cíle dostaneme, a to dokonce i včetně informací o směrovém značení | * výsledkem může být grafický element optimální trasy, ale i podrobný itinerář, přes které ulice nebo čísla silnic se do cíle dostaneme, a to dokonce i včetně informací o směrovém značení | ||
| - | * Service Areas | + | |
| * obslužnost | * obslužnost | ||
| * podle komunikace | * podle komunikace | ||
| - | * nejbližší středisko obsluhy (Closest Facility) | + | |
| * která spádová nemocnice (policejní služebna, obchod) je pro obyvatele z jednotlivých ulic nejbližší | * která spádová nemocnice (policejní služebna, obchod) je pro obyvatele z jednotlivých ulic nejbližší | ||
| - | * matice vzdáleností (OD Cost Matrix) | + | |
| * vygeneruje tabulku známou dříve z běžných autoatlasů, | * vygeneruje tabulku známou dříve z běžných autoatlasů, | ||
| - | * lokační analýza (Location) | + | |
| * umožní navrhnout optimální umístění střediska (výjezdové místo HZS) | * umožní navrhnout optimální umístění střediska (výjezdové místo HZS) | ||
| - | * alokační analýza (Alocation) | + | |
| * vypočítá obslužnost daného střediska (výjezdového místa HZS) | * vypočítá obslužnost daného střediska (výjezdového místa HZS) | ||
| - | * problém optimalizace provozu (Vehicle Routing Problem) | + | |
| * tak to je hustý! | * tak to je hustý! | ||
| * zákazníci, | * zákazníci, | ||
Permalink teorie_grafu.1484253359.txt.gz · Last modified: 2017/01/12 21:35 by efox
oeffentlich
