2. Základní pojmy / Orientované grafy
Zatím jsme používali pouze tzv. neorientované grafy - Pokud vedla hrana z vrcholu A do vrcholu B, vedla hrana také z B do A (nerozlišovali jsme směr hrany). Při popisu reálných situací pomocí grafů se nám často může stát, že hrana vede pouze jedním směrem - např. u silniční sítě by takový stav nastal u jednosměrné silnice.
Z takových důvodů zavádíme tzv. orientované grafy.
Obr. č. 2.26 - Příklad orientovaného grafu
Definice
Orientovaný graf G je dvojice (V,E), kde E je podmnožina kartézského součinu V × V. Prvky E nazýváme šipky nebo orientované hrany. Orientovaná hrana e má tvar (x, y). Říkáme, že tato orientovaná hrana vychází z x a končí v y.
Reprezentace pomocí matice sousednosti
Pokud pro reprezentaci grafu použijeme matici sousednosti, bude situace velmi podobná jako u neorientovaných grafů. Musíme si ovšem u souřadnic prvku uvědomit, že první číslo znamená odkud a druhé kam hrana vede. Přestává totiž platit, že hodnota prvku na souřadnicích např. (1,2) je stejná jako hodnota prvku na pozici (2,1). Proto také matice sousednosti orientovaného grafu není nutně symetrická.
Obr. č. 2.27 - Reprezentace orientovaného grafu pomocí matice sousednosti