Algorithmes de référence : Fermetures de graphe
Définitions et notations :
Une fermeture d'un graphe orientée G=(V,E) est obtenue en ajoutant des
arêtes.
– fermeture réflexive Go=(V,E+R) avec R={xx, x∈V}.
– fermeture symétrique Gs=(V,E+S) avec S={yx, xy∈E}.
– fermeture transitive G+=(V,E+T) avec T={xz, x≠y≠z et
xy∈E+T et yz∈E+T} (définition inductive).
– fermeture réflexo-transitive G*=(V,E+R+T) avec R et T
définis ci-dessus.
Inversement, la couverture ou diagramme de Hasse d'un graphe orienté est
obtenue en supprimant toutes les arêtes de réflexivité et de
transitivité du graphe.
N.B. On peut considérer la fermeture symétrique d'un graphe orienté comme une
transformation en graphe non orienté.
Par convention, on considère généralement que les graphes non-orientés n'ont
pas de boucles.
La fermeture réflexo-transitive d'un graphe antisymétrique (sans aucune arête
de symétrie) donne la plus petite relation d'ordre incluant ce graphe.
Pour utiliser la fermeture réflexive d'un graphe orienté G=(V,E), il suffira
d'adapter, dans les algorithmes utilisant cette fermeture, les tests
d'existence d'arête en conséquence : "xx∈E" sera toujours vrai.
La question est aussi simple pour la fermeture symétrique si E est représenté
par une matrice qui donne accès en O(1) au test de présence d'une arête, et
"xy∈E" sera remplacé par "xy∈E ou yx∈E", sans coût supplémentaire.
Il n'en va pas de même si E est représenté par des listes d'adjacence où la
symétrisation ne se fera plus en O(1) mais en temps linéaire.
schéma algorithmique FERMTRANS
Donnée : Un graphe orienté G=(V,E).
Résultat : Sa fermeture réflexo-transitive
G*=(V,E*).
E
*← E;
Pour x∈X
faire
Pourchaque sommet y atteint par PARCOURS(G,x)
faire
E*← E*+{xy}.
Complexité : O(n(n+m)) ou O(n3).
N.B. L'opérateur + est utilisé à la place de l'opérateur
∪ pour montrer que les deux ensembles sont disjoints : on n'ajoute à
E*que des arêtes qui ny 'étaient pas auparavant.
Cet algorithme est intéressant pour des graphes creux (càd avec peu d'arêtes)
ou réguliers.
algorithme Roy-Warshall
Donnée : Un graphe orienté G=(V,E) avec E sous forme matricielle
et n=|V|.
Résultat : La matrice M de sa fermeture réflexo-transitive.
//
// Ajouter les éléments diagonaux de M (I est la matrice diagonale)
M← E∨I;
Pour i de 1 à n
faire
Pour j de 1 à n
faire
Si M[j,i]=1
alors
Pour k de 1 à n
faire
Si M[i,k]=1 alors M[j,k]← 1.
Complexité : O(n3).
Cet algorithme est intéressant pour des graphes pleins (avec beaucoup
d'arêtes). On pourrait le transformer pour obtenir la couverture d'un graphe.
Théorème : Le calcul de la fermeture réflexo-transitive d'un
graphe orienté est un problème équivalent au produit de matrice.
La complexité du problème de multiplication de matrice est actuellement en
O(n2,376).