teorie_grafu

základní pojmy, klasifikace, příklady využití, algoritmy (optimalizační úlohy na grafech)

graf

http://voho.eu/wiki/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={h₁, h₂, …, h_n}
  - U je množina uzlů U={u₁, u₂, …, u_m}
  - ρ 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

Permalink teorie_grafu.txt · Last modified: 2017/09/21 16:31 by efox

oeffentlich