Table of Contents
základní pojmy, klasifikace, příklady využití, algoritmy (optimalizační úlohy na grafech)
graf
- = grafické vyjádření vztahů mezi objekty
- = dvojice disjunktních množin uzlů (vrcholů, vertex-vertices) a hran (edge-edges), přičemž hrana vždy spojuje právě dva uzly (které nemusí být různé)
- incidence = místu vstupu nebo výstupu hrany, vztah hrany s uzlem
- definice grafu
- graf je trojice G={H, U, ρ), kde:
- H je množina hran H={h1, h2, …, hn}
- U je množina uzlů U={u1, u2, …, um}
- ρ je indicenční funkce, která je dána předpisem:
- pro neorientovaný graf
- H → U ⊗ U (množina všech neuspořádaných dvojic prvků z množiny U)
- pro orientovaný graf
- H → U × U (kartézský součin - množina všech uspořádaných dvojic prvků z množiny U)
- kostra grafu
- libovolný podgraf spojující hranami všechny vrcholy původního grafu
- sám neobsahuje žádnou kružnici
- izomorfní graf
- něco s bijekcí (najdu si to!!!!)
- mají stejný počet vrcholů i hran
- hrany
- orientovaná, neorientovaná, násobné hrany, rovnoběžné hrany (jaký je rozdíl mezi násobnou a rovnoběžnou???, smyčka
- ohodnocená, neohodnocená
- vzdálenost, průchodnost, kapacita hrany pro přenos (informace, komodity)
- funkce, která dosazuje vrcholům hodnoty s jejich nejkratší vzdáleností = metrika (NUTNOST SOUVISLÉHO GRAFU)
typy grafů
podle smyček a rovnoběžných hran
- jednoduchý graf (obyčejný graf)
- nemá ani smyčky ani násobné hrany
- multigraf
- obsahuje násobné hrany (tzn. když jsou dva uzly spojeny více hranami) i smyčky
- pseudograf (prostý graf)
- obsahuje smyčky
podle orientace
- orientovaný
- všechny hrany jsou orientované
- vyjadřuje jednostranné (nesymetrické) vztahy mezi uzly
- neorientovaný
- všechny hrany jsou neorientované
- vyjadřuje oboustranné vztahy
- např. sourozenci
- smíšený
- obsahuje orientované i neorientované hrany
- v praxi se nepoužívá (spíš se nahradí orientovanými hranami - opačné směry)
podle souvislosti
- souvislé
- musí ∃ cesta mezi každou dvojicí vrcholů
- nesouvislé
podle ∃ kružnice v grafu
- cyklické
- acyklické
nakreslím ho do roviny bez křížení hran?
- rovinné
- nerovinné
souvislost grafu
- kružnice je uzavřená cesta
- z každého sledu lze vybrat cestu
- v souvislém grafu existuje cesta mezi každou dvojicí jeho uzlů
sled
- taková posloupnost vrcholů, že mezi každými po sobě dvěma jdoucími je hrana
- prostě to musí být spojení
tah
- sled, kde není žádná hrana víc než jedenkrát
- sled, kde se neopakují hrany
uzavřený tah
- končí tam kde začal. tak jak my.
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
- každá uzavřená cesta
cyklus
- uzavřená orientovaná cesta
reprezentace grafů
diagramem
definicí
maticí
- v hlavní diagonále jsou nuly (uvažujeme obyčejný graf bez smyček)
- 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
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íť
síťová analýzy
- silniční a uliční síť:
- délka
- průměrná rychlost
- ú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áší živá data o aktuální hustotě dopravy
- 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 je reprezentována polygonem s parametrem „zdržení“ s hodnotu 2 - při výpočtu bude trvat průjezd 2x déle
- 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ů, která informuje o vzdálenostech mezi jednotlivými městy
- 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, sklady a vozidla → rozvézt zboží mezi zákazníky v určitém čase → počítá i s kapacitou vozidla, závozovými okny, časy kdy jsou vozidla k dispozici