Qu'est-ce qu'un graphe orienté et quelles sont ses caractéristiques?

Un graphe orienté est un graphe qui possède un ensemble de sommets (nœuds) et un ensemble d'arêtes (arcs), où chaque arc a une direction.

Caractéristiques :

• Arêtes orientées : La circulation le long de l'arête n'est possible que dans une seule direction, indiquée par une flèche.
• Degré du sommet : Pour un graphe orienté, on définit le degré entrant (le nombre d'arêtes se terminant au sommet) et le degré sortant (le nombre d'arêtes commençant au sommet).
• Chemins et cycles : Un chemin est une séquence de sommets connectés par des arêtes dans la bonne direction. Un cycle est un chemin qui commence et se termine au même sommet. Les graphes orientés peuvent contenir des cycles orientés.
• Connectivité : On distingue la connectivité faible (en ignorant la direction des arêtes, le graphe est connexe comme non orienté) et la connectivité forte (pour tout pair de sommets A et B, il existe un chemin orienté de A à B et de B à A).
• Représentation : Ils peuvent être représentés par une liste d'adjacence ou une matrice d'adjacence, où pour un graphe orienté, la matrice n'est généralement pas symétrique.

Exemple de représentation par liste d'adjacence :

# Graphe G = (V, E), où V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

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

Exemple de représentation par matrice d'adjacence :

# Graphe G = (V, E), où 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]   # pas d'arêtes sortantes de 2
]