Co je orientovaný graf a jaké jsou jeho vlastnosti?

Orientovaný graf je graf, ktorý má množinu vrcholov (uzlov) a množinu hrán (šípok), pričom každá šípka má smer.

Vlastnosti:

• Smerované hrany: Pohyb po hrane je možný iba jedným smerom, ktorý je označený šípkou.
• Stupeň vrcholu: Pre orientovaný graf sa definuje vstupný stupeň (počet hrán končiacich vo vrchole) a výstupný stupeň (počet hrán začínajúcich vo vrchole).
• Cesty a cykly: Cesta je sekvencia vrcholov spojených hranami v správnom smere. Cykel je cesta, ktorá začína a končí v tom istom vrchole. Orientované grafy môžu obsahovať orientované cykly.
• Spojitosť: Rozlišujeme slabú spojitosť (ignorujúc smerovanie hrán, graf je nesmerovaný spojitý) a silnú spojitosť (pre akékoľvek dva vrcholy A a B existuje orientovaná cesta z A do B a z B do A).
• Zobrazenie: Môžu byť zobrazené pomocou zoznamov susednosti alebo matíc susednosti, pričom matica pre orientovaný graf zvyčajne nie je symetrická.

Príklad zobrazenia pomocou zoznamu susednosti:

# Graf G = (V, E), kde V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

graf = {
    0: [1],
    1: [2],
    2: [0]
}

Príklad zobrazenia pomocou matice susednosti:

# Graf G = (V, E), kde V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

matica = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # žiadne výstupné hrany z 2
]