Geografie dopravy - cvičení

                                                               Teorie grafů (pojmy, míry, indexy)

                                                                              Čtvrtek 17. 3. 2005

   

                                 Teorie grafů (pojmy, míry, indexy)

   

   Základní pojmy

   Graf = symbolické znázornění reálné sítě, abstrakce reality (realita = soustava propojených
   uzlů)

   

   Postup převodu reálné sítě do grafu - pravidla

   

   Základní pojmy:

   §         graf (G),

   §         vrchol (uzel) (v),

   §         hrana (e).

   §         hrana typu "most".

   

   Další pojmy:

   §         podgraf -- podmnožina grafu, která se zbytkem grafu není spojena žádnou hranou (je-li
   globální dopravní systém grafem, potom je dopravní síť každého druhu dopravy jeho podgrafem),

   §         planární (rovinný) × neplanární (3D) graf.

   

   Hrany, cesty apod.

   Protože dopravní sítě umožňují pohyb osob, zboží a informací, musí i teorie grafů nabízet
   možnosti znázornění takových pohybů -- pojmy:

   §         spojení -- každá soustava dvou vrcholů spojených hranou, mezi nimiž tedy existuje
   možnost pohybu, a to nezávisle na směru;

   §         cesta -- sled hran, které jsou absolvovány při přesunu z jednoho vrcholu do jiného ve
   stejném směru (nepřerušenost takového sledu).

   

   Každé hraně, každému spojení, každé cestě může být přisouzena charakteristika vzdálenosti
   (např. km, množství dopravy, čas, ...).

   

   §         cykly, okruhy

   

   §         strom -- graf bez cyklu

   

   Základní strukturální vlastnosti grafů

   Prostorová organizace uzlů a hran vyjadřuje strukturu grafu. K nejdůležitějším strukturálním
   vlastnostem grafu patří:

   §         symetrie × asymetrie grafu:

   --        symetrický je graf tehdy, pakliže existuje obousměrné spojení všech spojených
   vrcholů,

   --        jsou-li některé vrcholy spojeny pouze v jednom směru, pak je graf asymetrický;

   §         kompletnost grafu -- graf je kompletní tehdy, pokud je každý vrchol napojen minimálně
   jednou hranou alespoň v jednom směru (kompletní graf nemá podgrafy);

   §         konektivita grafu -- takový graf musí splňovat vlastnost, že z kteréhokoliv vrcholu
   existuje cesta do všech ostatních vrcholů (hraje roli směr).

   

   Analýza efektivity sítí -- míry a indexy

   K analýze efektivity sítí využívá teorie grafů řadu různých měr a indexů -- jejich využití:

   §         schopnost vyjádřit strukturu sítě prostřednictvím jedné hodnoty, jednoho čísla,

   §         srovnání různých dopravních sítí v určitém čase,

   §         srovnání vývoje dopravní sítě v různých obdobích.

   

   Míry:

   §         diametr (d) -- délka nejkratší cesty mezi dvěma nejvzdálenějšími vrcholy grafu (čím
   vyšší má síť d, tím méně je propojená);

   §         počet cyklů (cyklické číslo, u) -> u = e -- v + p;

   §         řád (stupeň) vrcholu (o) -- jde o míru udávající počet hran, jež vycházejí z určitého
   vrcholu, jedná se o jednoduchou, ale efektivní míru významu vrcholu (hub).

   

   Indexy -- komplexnější prostředky analýzy struktury sítí:

   §         detour index (deviatilita) -- ukazatel, jakým způsobem daná dopravní síť překonává
   vzdálenost či "odpor" prostředí

   DI = DT / DD

   DI -- detour index,

         DT -- reálná vzdálenost v dopravní síti,

         DD -- přímá (vzdušná) vzdálenost

   §         hustota sítě (v km hran / km^2);

   §         pí index -- vztah mezi celkovou délkou grafu L(G) a délkou diametru D(d) -- délky hran
   musí být v tomto případě oceněny, nejlépe v km;

   §         eta index -- průměrná délka hrany;

   §         theta index -- průměrné množství dopravy na jeden vrchol;

   §         iota index -- poměr mezi celkovou délkou sítě a celkovou "hmotou" vrcholů (jako váha
   se užívá stupeň vrcholu, který je v případě všech vrcholů stupně 2 a více násoben dvěma);

   

   §         beta index -- míra konektivity grafu, počítá se jako počet hran ku počtu vrcholů (čím
   vyšší hodnota, tím je graf konektivnější);

   b = e / v

   

   §         alfa index - míra konektivity grafu, počítá se jako počet cyklů ku maximálnímu
   možnému počtu cyklů (čím vyšší hodnota, tím je graf konektivnější);

   a = u / (2v -- 5)

   

   §         gamma index - míra konektivity grafu, počítá se jako počet hran ku maximálnímu
   možnému počtu hran (čím vyšší hodnota, tím je graf konektivnější);

   g = e / 3(v -- 2)