Lecture zen
Graphe orienté
[ Definition ]
Un graphe orienté est la donnée d’un couple \((X,U)\) où \(X\) est un ensemble muni d’une relation binaire \(U\). Les éléments de \(X\) sont appelés les sommets du graphe et les éléments de \(U\) sont appelés les arcs du graphe.
Si \(d^+(x)=0\) \(x\) est appelé un puits.
En savoir plus
On note \(\Gamma^+(x)\) l’ensemble des \(y\) tels que \((x,y) \in U\); on l’appelle ensemble des successeurs de \(x\).
On note \(\Gamma^-(x)\) l’ensemble des \(y\) tels que \((y,x) \in U\); on l’appelle ensemble des prédécesseurs de \(x\).
On note \(d^+(x)=|\Gamma^+(x)|\) le degré sortant ou degré externe de \(x\).
On note \(d^-(x)=|\Gamma^-(x)|\) le degré entrant ou degré interne de \(x\).
Si \(d^-(x)=0\) \(x\) est appelé une source.