Bonne numérotation des graphes orientés
Définition
Soit \( \G\) un graphe orienté. Une bonne numérotation sur \( \G\) est une application
\( N : \Som(\G) \longrightarrow \N\)
tel que
\[\forall (x,y) \in \Arc(\G), \quad N(x) {<} N(y)\]
Remarque
En particulier, il n'existe pas de bonne numérotation sur des graphes ayant des arc de la forme \( (x,x)\) .
Considérons par exemple le graphe suivant
\[\xymatrix@C=2cm{
&a\ar[dl]&b\ar[dd]\ar[lld]&\\
f\ar[rrd]&&&c\ar@/_3pc/[llu]\ar@/^3pc/[lld]\\
&e\ar@/^7pc/[uu]\ar[lu]\ar[ruu]\ar[r]&d&
}\]
Une bonne numérotation est par exemple:
\begin{eqnarray*}
N : \Som(\G)&\longrightarrow&\N\\
a&\longmapsto&3\\
b&\longmapsto&4\\
c&\longmapsto&1\\
d&\longmapsto&6\\
e&\longmapsto&2\\
f&\longmapsto&5
\end{eqnarray*}
Définition
Soient \( \G\) un graphe orienté et \( N\) une bonne numérotation sur \( \G\) . On définit le graphe orienté \( \G^N\) par
\[\Som(\G^N) = \left\{N(x)\big|x\in \Som(\G)\right\}\]
\[\Arc(\G^N) = \left\{(N(x),N(y))\big|(x,y)\in \Arc(\G)\right\}\]
Avec l'exemple précédent le graphe \( \G^N\) est
\[\xymatrix@C=2cm{
&3\ar[dl]&4\ar[dd]\ar[lld]&\\
5\ar[rrd]&&&1\ar@/_3pc/[llu]\ar@/^3pc/[lld]\\
&2\ar@/^7pc/[uu]\ar[lu]\ar[ruu]\ar[r]&6&
}\]
En réordonnant le graphe en écrivant les sommets par ordre croissant suivant la lecture on obtient :
\[\xymatrix@R=0.5cm@C=1.5cm{
&&3\ar[rd]&&\\
1\ar[r]\ar[rru]&2\ar[rr]\ar@/_3pc/[rrr]\ar[rd]&&5\ar[r]&6\\
&&4\ar[ru]\ar[rru]&&
}\]
Proposition
Soient \( \G\) un graphe orienté et \( N\) une bonne numérotation. La matrice booléenne de \( \G^N\) est une matrice triangulaire supérieure stricte.
Démonstration
Le coefficient \( M_{i,j}\) de la matrice booléenne du graphe \( \G^N\) vaut \( 1\) s'il existe un arc entre les sommets \( i\) et \( j\) . Mais par définition de bonne numérotation (\( N(x) {<} N(y)\) ) ces coefficients sont nuls lorsque \( i\geqslant j\) .
Remarque
En informatique, lorsque l'on est amené à manipuler des graphes, on utilise leur représentation matricielle. Plus le graphe possède de sommet, plus la matrice est grande et donc plus les boucles nécessaire pour parcourir le graphe sont longues ; de l'ordre de \( n^2\) . Avec un bonne numérotation, le résultat précédent stipule que, puisque la matrice est triangulaire supérieur, il n'est pas nécessaire de la parcourir en entier mais simplement de se cantonner à la partie supérieure, réduisant ainsi le nombre d'opération ; de l'ordre de \( \dpl{\frac{n(n-1)}{2}}\) .
Théorème
Un graphe orienté est sans circuit si et seulement s'il existe une bonne numérotation.
En lieu et place de la preuve de ce théorème, nous allons détailler un algorithme permettant d'une part, de déterminer si le graphe possède ou non un circuit et d'autre part, lorsqu'il n'en possédera aucun, donnera la bonne numérotation. Il s'agit de l'
algorithme de filtration (la preuve de ce théorème se résume à montrer que l'algorithme de filtration propose bien une bonne numérotation).
Définition
Soit \( x\) un sommet d'un graphe orienté \( \G\) .
- \( (i)\)
- On dira que \( x\) est un puits si \( \Gamma^{+1}(x,\G)=\varnothing\) .
- \( (ii)\)
- On dira que \( x\) est une source si \( \Gamma^{-1}(x,\G)=\varnothing\) .
Autrement : un puits est un sommet sans successeur et une source est un sommet sans prédécesseur.
\[\xymatrix@C=2cm{
&a\ar[dl]&b\ar[dd]\ar[lld]&\\
f\ar[rrd]&&&c\ar@/_3pc/[llu]\ar@/^3pc/[lld]\\
&e\ar@/^7pc/[uu]\ar[lu]\ar[ruu]\ar[r]&d&
}\]
Dans ce graphe le sommet \( c\) est une source et le sommet \( d\) est un puits.
Remarque
L'algorithme de filtration possède deux versions : l'algorithme de filtration par les sources et l'algorithme de filtration par les puits. Nous présentons celui par les sources qui est plus "naturel".
§ Algorithme de filtration par les sources.
1. Initialisation
n = 1 (l'indice de la numérotation)
Pour chaque sommet x du graphe
Pred[x] = les prédécesseurs de x.
Fin pour
S = les sources = les sommets x tel que Pred[x] soit vide.
2. Itérations
Tant que S est non vide
Numéroter les éléments de S en incrémentant n.
Supprimer les éléments de S dans le tableau Pred.
S = les sommets x non numéroté tel que Pred[x] soit vide.
Fin tant que
3. Conclusion
Si Pred est complètement vide
Le graphe est sans circuit.
La numérotation effectuée est une bonne numérotation.
Sinon
Le graphe possède au moins un circuit.
Fin si
Faisons tourner cet algorithme sur l'exemple
\[\xymatrix{
&a\ar[dl]&b\ar[dd]\ar[lld]&\\
f\ar[rrd]&&&c\ar@/_3.19pc/[llu]\ar@/^3.19pc/[lld]\\
&e\ar@/^7pc/[uu]\ar[lu]\ar[ruu]\ar[r]&d&
}\]
On représente les différentes variables du programme dans un tableau :
\[
\begin{array}{*{7}{|c}|}
\hline
x&a&b&c&d&e&f\\\hline
Num&&&&&&\\\hline
Pred&&&&&&\\
&&&&&&\\
&&&&&&\\\hline
\end{array}
\]
Première étape . L'initialisation.
\[
\begin{array}{*{7}{|c}|}
\hline
x&a&b&c&d&e&f\\\hline
Num&&&&&&\\\hline
Pred&c&e&&b&c&a\\
&e&&&e&&b\\
&&&&f&&c\\\hline
\end{array}
\]
On repère les colonnes vide : ici il n'y a que \( c\) . On numérote donc \( c\) à 1 et on supprime toutes les occurrences de \( c\) dans la case \( Pred\) .
\[
\begin{array}{*{7}{|c}|}
\hline
x&a&b&c&d&e&f\\\hline
Num&&&1&&&\\\hline
Pred&&e&&b&&a\\
&e&&&e&&b\\
&&&&f&&\\\hline
\end{array}
\]
On repère ensuite les cases vides non numérotées : il n'y a que \( e\) . On le numérote à 2 et on supprime les occurrences de \( e\) .
\[
\begin{array}{*{7}{|c}|}
\hline
x&a&b&c&d&e&f\\\hline
Num&&&1&&2&\\\hline
Pred&&&&b&&a\\
&&&&&&b\\
&&&&f&&\\\hline
\end{array}
\]
On repère les cases vides non numérotées : il y a \( a\) et \( b\) que l'on numérote 3 et 4 (ou 4 et 3 cela n'a pas d'importance). On supprime \( a\) et \( b\) du tableau
\[
\begin{array}{*{7}{|c}|}
\hline
x&a&b&c&d&e&f\\\hline
Num&3&4&1&&2&\\\hline
Pred&&&&&&\\
&&&&&&\\
&&&&f&&\\\hline
\end{array}
\]
Le \( f\) est la seul case vide non numéroté d'où
\[
\begin{array}{*{7}{|c}|}
\hline
x&a&b&c&d&e&f\\\hline
Num&3&4&1&&2&5\\\hline
Pred&&&&&&\\
&&&&&&\\
&&&&&&\\\hline
\end{array}
\]
Finalement
\[
\begin{array}{*{7}{|c}|}
\hline
x&a&b&c&d&e&f\\\hline
Num&3&4&1&6&2&5\\\hline
Pred&&&&&&\\
&&&&&&\\
&&&&&&\\\hline
\end{array}
\]
et le graphe est donc sans circuit.
