A. Sigayret : Algorithmique

Algorithmes de référence : Graphe sans circuit


Définitions et notations :
Un circuit dans un graphe orienté est une suite (x1,...,xk) de sommets tels que tous les xixi+1 et xkx1 sont des arcs du graphe. Si k=1, le circuit est appelée une boucle.
Une source est un sommet qui n'est le successeur de personne (son degré entrant est nul).
Un puits est un sommet qui n'a aucun successeur (son degré sortant est nul).
Une extension linéaire d'un graphe G=(V,E) est un ordre strict total P=(V,F) tel que E⊆F.

Théorème : Un graphe orienté est sans circuit quand il possède une source (resp. un puits) et que tous ses sous-graphes sont sans circuit.
Remarque. Démonstration par contraposition.
 
schéma algorithmique S-SEQUENCE
Donnée : Un graphe orienté.
Résultat : ce graphe est-il sans circuit (vrai/faux).
Tantque le graphe possède au moins une source faire :
Supprimer toutes les sources du graphe;
Le graphe est sans circuit ssi il ne reste plus de sommets.
 
Preuve de résutat : On réalise un schéma d'élimination de sources successives. Quand il n'y a plus de source, on utilise le théorème précédent.

algorithme S-SEQUENCE
Donnée : Un graphe orienté G=(V,E).
Résultat : G est-il sans circuit (vrai/faux). Une numérotation Num des sommets de G.
i←0;
H← G;
S← Source(H);
Tanque S≠∅ faire
CHOISIR x dans S;
i←; i+1;
Num[x]← i;
H← H−{x};
S=Source(H);
Si H n'a plus aucun sommet
alors Retourner Vrai
sinon Retourner Faux.
 
Complexité : réalisable en O(n+m).

Théorème : La numérotation Num obtenue correspondant à une extension linéaire de G compatible avec un schéma d'élimination des sources successives.
 
schéma algorithmique ARCRETOUR
Donnée : un graphe orienté G=(V,E).
Résultat : G est-il sans circuit (vrai/faux).
Réaliser une exploration en profondeur de G en testant la présence d'arc retour.
Si un arc retour est trouvé alors Retourner Faux.
sinon Retourner vrai à la fin du parcours.
 
Complexité linéaire.