Smerovaný verzus nepresmerovaný graf
Graf je matematická štruktúra, ktorá sa skladá z množiny vrcholov a hrán. Graf predstavuje množinu objektov (reprezentovaných vrcholmi), ktoré sú spojené cez nejaké väzby (reprezentované hranami). Pomocou matematických zápisov je možné graf znázorniť pomocou G, kde G=(V, E) a V je množina vrcholov a E je množina hrán. V neorientovanom grafe nie je žiadny smer spojený s hranami, ktoré spájajú vrcholy. V orientovanom grafe je smer spojený s hranami, ktoré spájajú vrcholy.
Neorientovaný graf
Ako už bolo spomenuté, neorientovaný graf je graf, v ktorom nie je žiadny smer na hranách, ktoré spájajú vrcholy v grafe. Obrázok 1 znázorňuje neorientovaný graf s množinou vrcholov V={V1, V2, V3}. Množinu hrán vo vyššie uvedenom grafe je možné zapísať ako V={(V1, V2), (V2, V3), (V1, V3)}. Dá sa tiež poznamenať, že nič nebráni zápisu množiny hrán ako V={(V2, V1), (V3, V2), (V3, V1)}, keďže hrany nemajú smer. Preto hrany v neorientovanom grafe nie sú usporiadané páry. Toto je hlavná charakteristika neorientovaného grafu. Neorientované grafy možno použiť na znázornenie symetrických vzťahov medzi objektmi, ktoré sú reprezentované vrcholmi. Napríklad obojsmernú cestnú sieť, ktorá spája množinu miest, možno znázorniť pomocou neorientovaného grafu. Mestá môžu byť znázornené vrcholmi v grafe a okraje predstavujú obojsmerné cesty, ktoré spájajú mestá.
Smerovaný graf
Smerovaný graf je graf, v ktorom majú hrany v grafe, ktoré spájajú vrcholy, smer. Obrázok 2 znázorňuje orientovaný graf s množinou vrcholov V={V1, V2, V3}. Množinu hrán vo vyššie uvedenom grafe je možné zapísať ako V={(V1, V2), (V2, V3), (V1, V3)}. Hrany v neorientovanom grafe sú usporiadané páry. Formálne môže byť hrana e v orientovanom grafe reprezentovaná usporiadanou dvojicou e=(x, y), kde x je vrchol, ktorý sa nazýva počiatok, zdroj alebo počiatočný bod hrany e, a vrchol y sa nazýva koniec., ukončujúci vrchol alebo koncový bod. Napríklad cestnú sieť, ktorá spája množinu miest pomocou jednosmerných ciest, možno znázorniť pomocou neusmerneného grafu. Mestá môžu byť v grafe znázornené vrcholmi a orientované hrany predstavujú cesty, ktoré spájajú mestá vzhľadom na smer, ktorým na ceste prúdi doprava.
Aký je rozdiel medzi riadeným grafom a neorientovaným grafom?
V orientovanom grafe je hrana usporiadaná dvojica, kde usporiadaná dvojica predstavuje smer hrany, ktorá spája dva vrcholy. Na druhej strane v neorientovanom grafe je hrana neusporiadaným párom, pretože s hranou nie je spojený žiadny smer. Neorientované grafy možno použiť na znázornenie symetrických vzťahov medzi objektmi. In-stupeň a out-stupeň každého uzla v neorientovanom grafe je rovnaký, ale to neplatí pre orientovaný graf. Pri použití matice na znázornenie neorientovaného grafu sa matica vždy stane symetrickým grafom, ale to neplatí pre orientované grafy. Neorientovaný graf možno previesť na orientovaný graf nahradením každej hrany dvoma smerovanými hranami idúcimi v opačnom smere. Nie je však možné previesť orientovaný graf na neorientovaný graf.
