Cos'è un grafo orientato e quali sono le sue caratteristiche?

Un grafo orientato è un grafo che ha un insieme di vertici (nodi) e un insieme di archi (frecce), dove ogni arco ha una direzione.

Caratteristiche:

• Archi orientati: Il movimento lungo l'arco è possibile solo in una direzione, indicata da una freccia.
• Grado del vertice: Per un grafo orientato, si definiscono il grado in ingresso (numero di archi che terminano nel vertice) e il grado in uscita (numero di archi che partono dal vertice).
• Percorsi e cicli: Un percorso è una sequenza di vertici collegati da archi nella direzione corretta. Un ciclo è un percorso che inizia e termina nello stesso vertice. I grafi orientati possono contenere cicli orientati.
• Connettività: Si distingue tra connettività debole (ignorando le direzioni degli archi, il grafo è connesso come non orientato) e connettività forte (per ogni coppia di vertici A e B, esiste un percorso orientato da A a B e da B a A).
• Rappresentazione: Possono essere rappresentati tramite liste di adiacenza o matrici di adiacenza, dove per un grafo orientato, la matrice di solito non è simmetrica.

Esempio di rappresentazione tramite lista di adiacenza:

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

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

Esempio di rappresentazione tramite matrice di adiacenza:

# Grafo G = (V, E), dove 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]   # nessun arco in uscita da 2
]