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:03] efox [nakreslím ho do roviny bez křížení hran?] |
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 23: | Line 30: | ||
| * ohodnocená, | * ohodnocená, | ||
| * vzdálenost, | * vzdálenost, | ||
| - | * | + | * funkce, která dosazuje vrcholům hodnoty s jejich nejkratší vzdáleností = metrika (NUTNOST SOUVISLÉHO GRAFU) |
| - | * | + | |
| - | + | ||
| ====== typy grafů ====== | ====== typy grafů ====== | ||
| Line 75: | 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 91: | Line 97: | ||
| * v hlavní diagonále jsou nuly (uvažujeme obyčejný graf bez smyček) | * v hlavní diagonále jsou nuly (uvažujeme obyčejný graf bez smyček) | ||
| * u neorientovaného grafu je symetrická podle hlavní diagonály | * u neorientovaného grafu je symetrická podle hlavní diagonály | ||
| + | * vím | ||
| + | * **matice sousednosti** | ||
| + | * počet hran mezi dvěma sousedními uzly | ||
| + | * vím | ||
| + | * {{:: | ||
| ===== datovými strukturami ===== | ===== datovými strukturami ===== | ||
| + | ===== matematicky ===== | ||
| + | * **seznam sousedů / seznam vrcholů se seznamem hran** | ||
| + | * {{:: | ||
| + | * **indidenční matice** | ||
| + | * matice sousednosti má UZLY a UZLY v X i Y | ||
| + | * tohle to má nahoře HRANY a vlevo UZLY | ||
| + | * {{:: | ||
| + | * **matice dosažitelnosti** | ||
| + | * je jenom dole pod diagonálou | ||
| + | * johooo, pokud do toho čísla existuje sled, tak 1! jinak nula. | ||
| + | * takže když nevede nic do 7, tak bude mít celý prázdný řádek | ||
| + | ====== strom ====== | ||
| + | * souvislý graf | ||
| + | * neobsahuje kružnici | ||
| + | * mezi každými dvěma vrcholy existuje právě jedna cesta | ||
| + | * je to datová struktura | ||
| + | ====== úlohy ====== | ||
| + | ===== hledání nejkratší cesty===== | ||
| + | * Dijkstrův algoritmus | ||
| + | * ne záporná délka | ||
| + | * Bellman-Fordův | ||
| + | * i záporné hrany | ||
| + | ===== hledání minimální kostry===== | ||
| + | * Kruskalův algoritmus | ||
| + | * je hladový | ||
| + | ===== hledání maximální kostry===== | ||
| + | ====== toky v sítích ====== | ||
| + | * pomocí grafů můžeme řešit problém nalezení maximálního toku v síti | ||
| + | * vodovodní potrubí, dopravní síť, datová síť | ||
| - | ====== strom ====== | + | ===== síťová analýzy |
| - | * souvislý graf | + | * silniční a uliční síť: |
| - | * neobsahuje kružnici | + | * délka |
| - | * mezi každými dvěma vrcholy existuje právě jedna cesta | + | * průměrná rychlost |
| - | * je to datová struktura | + | * úprava na základě podmínky (na sněhu snížím o 20 %) |
| + | * speciální ohodnocení - historická hustota dopravy //(to se musím podívat!)// | ||
| + | * TMC = Trafic Message Channel - pokud je v daném místě k dispozici, přenáší | ||
| + | * omezení (restrictions) | ||
| + | * protože: šířka komunikace (max. povolená čířka vozidla), nosnost mostů, průjezdní výšky podjezdů | ||
| + | * definice směru jízdy | ||
| + | * bariéry | ||
| + | * geografický prvek (bod, linie, plocha), který lze do sítě dynamicky vložit | ||
| + | * zákaz (restriction) nebo zdržení (scaled cost) | ||
| + | * dočasná uzavírka: uzavření jednoho úseku silnice v síti, stačí jej „přeškrtnout“ krátkou úsečkou liniové bariéry, trasa tomuto úseku vždy vyhne | ||
| + | * plošná bariéra charakteru „zdržení“ může být situace, kdy se má algoritmus hledání optimální trasy vyhnout určité oblasti. Např. hustě obydlená oblast | ||
| + | * odbočitelnost | ||
| + | * např. jako čas nezbytný na odbočení můžu zahrnout do výpočtu (jakože doleva odbočit bývá těžší a delší) | ||
| + | * zákaz odbožení (jednoduchý - nesmím odbožit vlevo, složený - světelná křižovatka) | ||
| + | ==== úlohy ==== | ||
| + | * **hledání trasy z A do B** | ||
| + | * 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í | ||
| + | * **Service Areas** | ||
| + | * obslužnost | ||
| + | * podle komunikace | ||
| + | * **nejbližší středisko obsluhy (Closest Facility)** | ||
| + | * 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ů, | ||
| + | * **lokační analýza (Location)** | ||
| + | * 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) | ||
| + | * **problém optimalizace provozu (Vehicle Routing Problem)** | ||
| + | * tak to je hustý! | ||
| + | * zákazníci, | ||
Permalink teorie_grafu.1484251394.txt.gz · Last modified: 2017/01/12 21:03 by efox
oeffentlich
