Un Circuit ou Cycle (Orienté) est un chemin (orienté) menant d'un sommet à lui-même
La Longueur du circuit est la longueur du chemin sous-jacent
Exemple : \(0 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 0\) est un circuit de longueur \(4\)
Un graphe orienté sans aucun circuit est un graphe orienté acyclique,
ou Directed Acyclic Graph (DAG)
Exemples d'utilisation des Graphes Orientés Acycliques - DAG
Les DAG sont utilisés pour :
les cryptomonnaies et la blockchain
le logiciel de versionning Git
les chemins des Labyrinthes parfaits (càd sans sycles)
Un graphe orienté est dit simplement connexe, ou faiblement connexe, ou connexe, si en remplaçant chaque arc orienté par une arête non orientée, on obtient ainsi un graphe non orienté (dit associé) qui soit connexe.
Un graphe orienté dans lequel deux sommets quelconques sont toujours connectés par un chemin orienté (de l'un vers l'autre), est appelé un graphe fortement connexe
Graphe NON Fortement Connexe
Graphe Fortement Connexe
Pte
Un graphe orienté est fortement connexe \(\Leftrightarrow\) Quels que soient les sommets s et v de G :
Il existe toujours un chemin orienté de s vers v
Il existe toujours un chemin orienté de v vers s
\(\Leftrightarrow\) Quels que soient les sommets s et v de G, il existe un circuit passant par s et v
Exemple le graphe d'un réseau social est connexe, mais pas le graphe du réseau routier mondial n'est PAS connexe
Lorsque le graphe orienté est composé de plusieurs "morceaux" (en fait de plusieurs sous-graphes "induits" par un sous-ensemble de sommets, qui peuvent -ou pas- être reliés entre eux par des arêtes du graphe) dont chacun est fortement connexe, chaque morceau est appelé une composante connexe forte ou une composante fortement connexe.
Chaque couleur représente une Composante Fortement Connexe
Pte
Chaque composante fortement connexe est fortement connexe
Deux sommets quelconques d'une composante fortement connexe sont toujours connectés (reliables par un chemin orienté)
ou 