Ce este un graf orientat și care sunt caracteristicile sale?

Un graf orientat este un graf care are un set de vârfuri (noduri) și un set de muchii (săgeți), unde fiecare săgeată are o direcție.

Caracteristici:

• Muchii orientate: Mișcarea de-a lungul muchiei este posibilă doar într-o singură direcție, indicată de o săgeată.
• Gradul vârfului: Pentru un graf orientat, se definește gradul de intrare (numărul de muchii care se termină în vârf) și gradul de ieșire (numărul de muchii care încep din vârf).
• Căi și cicluri: O cale este o secvență de vârfuri conectate prin muchii în direcția corectă. Un ciclu este o cale care începe și se termină în același vârf. Graficele orientate pot conține cicluri orientate.
• Conectivitate: Se distinge între conectivitatea slabă (ignorând direcțiile muchiilor, graful este conex ca grafic neorientat) și conectivitatea puternică (pentru orice două vârfuri A și B, există o cale orientată de la A la B și de la B la A).
• Reprezentare: Pot fi reprezentate prin liste de adiacență sau matrici de adiacență, unde pentru un graf orientat, matricea în general nu este simetrică.

Exemplu de reprezentare cu ajutorul listei de adiacență:

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

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

Exemplu de reprezentare cu ajutorul matricei de adiacență:

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

matrice = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # nu există muchii de ieșire din 2
]