Fonction rang d'un graphe
Graphes sans circuit
Nous nous intéressons ici à l'ensemble des graphes qui ne contiennent ni boucles ni circuits.
Donc quelque soit le point x, il n'existe pas de chemin de x à x.
Remarque :
Un graphe est sans circuit s'il ne contient que des chemins élémentaires.
Définition : Fonction ordinale d'un graphe
On considère un graphe orienté G=(X,E) et on associe à chaque point x de E une valeur entière notée f(x).
La fonction f est une fonction ordinale du graphe G si l'existence d'un chemin non vide de x à y implique f(x)<f(y).
En conséquence, si l'on parcourt un chemin x1, x2, ..., xp, on a obligatoirement f(x1)<f(x2)<...<f(xp).
Définition : Fonction rang d'un graphe
La fonction rang d'un graphe est un cas particulier de fonction ordinale où :
- les points sans prédécesseurs ont comme valeur 0,
- tout autre point à une valeur la plus petite possible supérieure ou égale à la valeur de ses prédécesseurs augmentée de 1.
Structures de données utilisées dans l'algorithme de recherche de la fonction rang
La matrice en nombres entiers 0 ou 1 correspondant à la matrice booléenne B associée au graphe :
B(i,j) = 1 s'il existe un arc de i à j et 0 sinon
(B(i,i)=0 : pas de boucle en i).
Un tableau de marques M qui indique si la fonction rang a déjà été calculée pour un point ou pas :
M(i) = 1 si la fonction rang a déjà été calculée pour un point et 0 sinon.
Il est à noter que l'on aurait pu également utiliser le tableau de la fonction rang en lui donnant, par exemple une valeur +∞ quand la valeur n'est pas encore calculée, mais l'algorithme sera plus lisible en utilisant ce tableau de marques.
Un tableau NBPréd qui compte, pour chaque point son nombre de prédécesseurs non encore marqués.
Le nombre de points du graphe est noté n.
Les rangs calculés sont rangés dans le tableau R.
Algorithme de calcul de la fonction rang d'un graphe
Initialisation
Pour tout point i faire
Aucun point n'est marqué
M(i)=0 ;
Calcul du nombre de prédécesseurs de tout point
ndp=0 ;
Pour tout point j faire
si B(j,i)>0 alors ndp++ finsi
Fin pour j
NBPréd(i)=ndp ;
Fin pour i
Nombre de points marqués initialisés à 0
NBPM=0 ;
Valeur courante de la fonction rang
rang=-1 ;
L'algorithme est arrêté si on s'aperçoit que le graphe contient un circuit,
car dans ce cas il est impossible de calculer la fonction rang pour tous les points
circuit = faux ;
Itérations
Tantque NBPM<n et circuit = fauxfaire
une_modif=faux ;
rang=rang+1 ;
Pour tout i faire
si M(i) = 0 et NBPréd(i) = 0 alors
M(i)=1 ; NBPM=NBPM+1 ;
R(i)=rang ;
une_modif=vrai ;
finsi
Fin pour i
si une_modif = faux alors
Le graphe contient un circuit
circuit = vrai ;
sinon
On n'a pas encore détecté que le graphe contient un circuit.
si NBPM<n alors
Il reste des points non marqués.
Les points marqués sont devenus plus nombreux.
Il faut changer le tableau du nombre de prédécesseurs non marqués.
Pour tout point i faire
Calcul du nombre de prédécesseurs non marqués de tout point
ndp=0 ;
Pour tout point j faire
si B(j,i)>0 et M(j)=0 alors ndp++ finsi
Fin pour j
NBPréd(i)=ndp ;
Fin pour i
finsi
finsi
Fin tantque
Si circuit = vrai alors
Le graphe contient un circuit et la fonction rang ne peut être calculé.
sinon
Le tableau R contient le rang de tout point
finsi.
Déroulement de la fonction rang sur des graphes
Cliquez sur Anim pour démarrer l'animation. Choisissez un graphe avec les boutons précédent et suivant. Il est à noter que changer le graphe réinitialise l'algorithme. Utilisez en alternance d-IT et f-IT pour voir se dérouler l'algorithme sur le graphe et sur la matrice en variable 0-1. Le nombre de prédécesseurs des points non marqués de l'itération précédente est mis en bas de la matrice. On a essayé d'utiliser des couleurs. Le gris pour les modifications précédentes et le jaune pour les points intéressants de l'itération en cours.
Complexité de l'algorithme
La complexité de l'algorithme dépend de la représentation choisie du graphe.
Si le graphe est représenté par la liste des prédécesseurs des points. La représentation est proportionnelle au nombre d'arcs. Le comptage du nombre de prédécesseurs est alors proportionnel au nombre d'arcs et il y a au plus n itérations. L'algorithme est alors en O(nm).
Si le graphe est représenté par la matrice en valeurs entières 0-1. Le comptage du nombre de prédécesseurs est en n2 et il y a également n itérations au plus. L'algorithme est en O(n3).
