Fermeture transitive d'un graphe : Warshall

Sommaire du document

Matrice d'accessibilité

La notion d'accessibilité en théorie des graphes est la possibilité d'atteindre un sommet y depuis un sommet x.

Le sommet y est accessible depuis un sommet x soit si x = y (chemin de longueur nulle), soit si il existe un chemin entre x et y.

Nous utiliserons pour les chemins d'un sommet à lui même la matrice d'identité (I) de la manière suivante : M' = IA1A2⊕ ... ⊕An qui peut en pratique se simplifier par M'=(IA)n-1.

Fermeture transitive

Lorsque nous nous posons la question de savoir s'il existe des chemins entre deux sommets d'un graphe, nous ne sommes pas forcés de déployer l'artillerie lourde.

Mais lorsque nous nous posons souvent la question pour un même graphe, ou lorsque nous désirons savoir si il existe un chemein entre x et y pour tout x et pour tout y du graphe, alors nous avons besoin de calculer la fermeture transitive.

Calculer la fermeture transitive d'un graphe en pré-traitement révèle souvent un gain important lors de traitement ultérieur.

L'algorithme le plus répendu pour le calcul de la fermeture transitive d'un graphe est l'algorithme de Roy et Warshall[1]

 

Algorithme de Roy-Warshall

Fonctionnalités de l'algorithme de Roy-Warshall

L'algorithme de Roy-Warshall est un algorithme de recherche de fermeture transitive d'un graphe.

Caractéristiques de l'algorithme de Warshall

L'algorithme de Roy-Warshall nous permet de calculer aisément la matrice booléenne de la relation d'accessibilité, en jouant sur le double emploi d'une variable.

Warshall évite donc d'implémenter un algorithme de type M := IA1A2⊕ ... ⊕An qui se révèle beaucoup trop complexe.

La variable k joue donc un double rôle dans notre algorithme :

  • Indice de boucle : nous constatons que la boucle principale utilise k comme compteur d'itérations, de 0 (chemins de longueur 0, donc sans sommet intermédiaire), jusque n (nous avons alors envisagé tous les chemins passant par n'importe quel sommet intermédiaire).
  • Indice de sommet : M[i,k] et M[k,j].

 

Code de l'algorithme de Warshall

Variables

Phase d'initialisation

  • (i,j) M[i,j] := Aij=1?true:false;[2] // Toutes les valeurs 1 de la matrice A sont représentés par true dans le tableaux de tableaux M. Les valeurs 0 sont représentés par false.

Phase d'exécution


Code (Pseudo-code de Warshall) (9 lignes) :
  1. si M[i,k] = true alors
  2. M[i,j] ;:= M[i,j] ;⊕ ;M[k,j];

Comme l'algorithme de Warshall pour le calcul de la fermeture transitive se base sur l'emploi de matrices, nous allons travailler avec un tableau de tableaux, ce qui est identique, mais assez coûteux.

 

Algorithme de Minoux

Fonctionnalités de l'algorithme de Minoux

  • L'algorithme de Minoux est un algorithme de recherche de fermeture transitive d'un graphe.
  • Minoux n'accepte pas les circuits.
  • Complexité en général inférieure à celle de l'algorithme de Warshall.

Caractéristiques de l'algorithme de Minoux

Si nous avons la certitude que notre graphe ne présente pas de circuit, nous pouvons encore améliorer la recherche de fermeture transitive de notre graphe grace à l'ordre topologique sous-jacent, comme le propose Minoux[ref 2]. Cette amélioration se marque le plus avec les graphes de faible densité.

Dans le pire des cas, la complexité de l'algorithme de Minoux est de Ordre de grandeur(m*n) pour chaque arc, avec m pour le nombre d'arcs et n pour le nombre de sommets, donc Ordre de grandeur(n3)

Il existe aussi la version de Minoux et Bartnik, pour laquelle nous avons une complexité de Ordre de grandeur(∑dintj . dextj).

 

Réseaux sociaux

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Nuage de mots clés

25 mots clés dont 20 définis manuellement (plus d'information...).

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher le nuage de mots clés.

 

Notes

  1.  Warshall : Stephen Warshall (1935 - 11 Décembre 2006), à travaillé pour la recherche et le développement dans des domaines tels que les logiciels d'exploitation, la conception de compilateur, les langages de programmation, et la recherche opérationnelle.

  2.  M[i,j] := Aij=1?true:false : Voir la syntaxe de l'opérateur ternaire.

 

Références

  1. livre Langue du document: fr INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (Septembre 2008)
  2. livre Langue du document: fr Graphes et algorithmes : Michel Gondran; Michel Minoux, Eyrolles - 1995 3eme ed. rev. et augm.

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

 

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-9724
Document créé le 03/01/10 02:02, dernière modification le Mercredi 28 Juin 2017, 15:26
Source du document imprimé : http:///www.gaudry.be/graphes-fermeture-transitive.html
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Apparence (afficher)
Stats (afficher)
15838 documents
455 astuces.
550 niouzes.
3107 definitions.
447 membres.
8121 messages.

Document genere en :
0,09 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
Pensez qu'il y a un million de singes derrière un million de claviers, mais n'imaginez pas que les forums aient quoi que ce soit de comparable avec Shakespeare.

Blair Houghton
 
l'infobrol
Nous sommes le Lundi 24 Juillet 2017, 22:52, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)