Mi az az irányított gráf és mik a jellemzői?

Egy irányított gráf olyan gráf, amelynek csúcsai (csomópontjai) és élei (nyilak) vannak, ahol minden nyíl egy irányt jelez.

Jellemzők:

• Irányított élek: Az élen való mozgás csak egy irányban lehetséges, amit egy nyíl jelez.
• Csúcs fokszáma: Egy irányított gráf esetén meghatározzuk a bemeneti fokszámot (az élek száma, amelyek a csúcsba érnek) és a kimeneti fokszámot (az élek száma, amelyek a csúcsból indulnak).
• Út és ciklus: Egy út egy csúcsokból álló sorozat, amelyeket élek kötnek össze a helyes irányban. Egy ciklus egy olyan út, amely ugyanabból a csúcsból kezdődik és végződik. Az irányított gráfok tartalmazhatnak irányított ciklusokat.
• Kapcsolat: Különbséget teszünk gyenge kapcsolat (amikor az élek irányát figyelmen kívül hagyva a gráf nem irányítottan összefüggő) és erős kapcsolat (amikor bármely két csúcs A és B között létezik irányított út A-ból B-be és B-ből A-ba).
• Ábrázolás: Listával vagy mátrixszal lehet ábrázolni, ahol az irányított gráf esetén a mátrix általában nem szimmetrikus.

Példa listás ábrázolásra:

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

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

Példa mátrixos ábrázolásra:

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

mátrix = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # nincs kimenő él 2-ből
]