Algorithmes de référence : Connexité de graphe
Définitions et notations :
Un chemin dans un graphe non-orienté est une suite de sommets
x1,...xk) telle que ∀i∈[1;k−1]
xixi+1∈V. k est la longueur de ce chemin.
Un chemin est dit élémentaire quand tous les xi sont distincts.
Un graphe non-orienté est dit connexe quand il existe un
chemin entre chaque paire de sommets du graphe. Un graphe orienté est
dit connexe quand sa fermeture symétrique (càd le graphe non orienté
correspondant) est connexe.
Une composante connexe d'un graphe non-orienté G=(V,E) est une partie
Vi non vide de E telle que le sous-graphe correspondant
G(Vi) est connexe et de taille maximale pour cette propriété.
Une chaine dans un graphe orienté est une suite de sommets
x1,...xk) telle que ∀i∈[1;k−1]
xixi+1∈V (N.B. mais on n'a pas forcément
xi+1xi). k est la longueur de cette chaine.
Chaque xi est un descendant de x1 et
un ascendant de xk, notés xi∈Des(x)
et xi∈Asc(x).
Une chaine est dite élémentaire quand tous les xi sont distincts.
Un graphe orienté est dit fortement connexe quand il
existe une chaine entre chaque couple de sommets du graphe (N.B. pour deux
sommets x et y, on a deux couples (x,y) et (y,x)).
Une composante fortement connexe d'un graphe orienté G=(V,E) est une partie
Vi non vide de E telle que le sous-graphe correspondant
G(Vi) est fortement connexe et de taille maximale pour cette
propriété.
Le dual ou symétrique d'un graphe orienté G=(V,E)
est le graphe Dual(G)=(V,E−={yx, xyin;E}).
schéma algorithmique CC
Donnée : Un graphe non-orienté G.
Résultat : Les composantes connexes de G.
Tantque il reste un sommet x non atteint de G
faire
PARCOURS(G,x) construit la composante connexe de x dans G.
Preuve et complexité : on réalise, en temps linéaire, une
exploration du graphe, et chaque parcours s'effectue dans un sous-graphe
disjoint (noter la différence d'avec un graphe orienté).
Théorème :
La composante fortement connexe (CFC) d'un sommet est l'intersection de ses
ascendants et descendants (ce sommet compris).
N.B. cela revient à déterminer les composantes connexes de la
fermeture symétrique du graphe orienté.
algorithme CFC-AscDes
Donnée : un graphe orienté G.
Résultat : Partition des sommets de G en CFC.
G
−← Dual(G);
Tantque il reste un sommet x non classé
faire
// DesG−(x)=AscG(x)
Classer tous les sommets de DesG(x) et
DesG−(x) dans la composante de x.
Complexité O(n (n+m)) ou O(n3), pas efficace.
schéma algorithmique CFC-circuit
Donnée : un graphe orienté.
Résultat : Partition des sommets du graphe en CFC.
Explorer en profondeur le graphe en empilant à mesure les sommets et
chaque fois qu'il y a un arc retour xy dépiler juqu'à y pour former une CFC.
// équivalence entre présence d'arc retour et présence de circuit
Complexité : faisable en linéaire car la fonction Post du parcours
assure le test de présence d'un arc retour en O(1).
algorithme CFC-magique
Donnée : un graphe orienté.
Résultat : Partition des sommets du graphe en CFC.
Explorer en profondeur le graphe et récupérer la fonction Post;
Calculer le dual G− de G;
Explorer G− en choisissant à chaque étape un sommet x non
atteint de valeur Post(x) maximale :
Chacune de ces étapes donne une CFC du graphe.
Complexité : linéaire.
Preuve de résultat : difficile malgré la simplicité apparente de
l'algorithme.
Théorème : L'ordre d'obtention des CFC par CFC-magique fournit une
extension linéaire du graphe quotient du graphe initial par la relation
d'équivalence CFC entre sommets.