11/12/2010
Graphes
On s'intéresse ici au cas le plus général d'un ensemble muni d'une relation binaire . est un graphe orienté. On note l'ensemble des tels que ; on l'appelle ensemble des successeurs de . Théorème Soit un graphe orienté fini. est sans circuit si et seulement si les deux énoncés suivants sont vérifiés: Théorème Soit un graphe orienté fini. est sans circuit si et seulement si il existe une permutation des sommets tels que où . Ci-dessous un algorithme déterminant si oui ou non un graphe est sans circuit ou non. Procédure sans-circuit() La complexité de cet algorithme est avec le nombre de sommets et le nombre d'arcs. Un tri topologique d'un graphe orienté sans circuit est une permutation de telle que . Notons que la permutation calculée par l'algorithme précédent (ie. l'ordre de sortie de Source) est un tri topologique. L'algorithme suivant sert à engendrer tous les tris topologiques: Procédure Tri-topologique() avec la procédure récursive «Tri-topo» suivante: Tri-topo( ) La complexité est en . On considère maintenant un graphe orienté et sans circuits. On pose si et sinon; est appelé hauteur de . Algorithme de construction des niveaux du graphe; un niveau est de la forme : Il y a des circuits si et seulement si à la fin de l'algorithme nb-sommets est différent de . Un chemin sur un graphe est un n-uplet tel que . Lemme: On déduit de ce lemme un algorithme destiné à déterminer la fermeture transitive d'un graphe, l'algorithme de Roy-Warshall: On peut constater que l'on n'applique pas exactement le lemme, car les ne sont pas les bons, mais l'on peut aussi montrer que l'algorithme fonctionne tout de même. La complexité de l'algorithme de Roy-Warshall est . Soit un graphe orienté, est une réduction transitive de si , n'a pas de transitivité et . Algorithme général de calcul d'une fermeture transitive (pas seulement dans le cas d'un graphe sans circuit). Le coût de cet algorithme est . On cherche maintenant à déterminer à la fois la fermeture et la réduction transitive dans un graphe sans circuit. Pour tout faire La complexité est en . Problèmes ouverts: peut on réaliser la fermeture transitive de en ? La réduction transitive en ? Comment détecter qu'un graphe est fermé transitivement ? Réduit transitivement ? (probablement faisable en temps linéaire) Graphes
On note l'ensemble des tels que ; on l'appelle ensemble des prédécesseurs de .
On note le degré sortant ou degré externe de .
On note le degré entrant ou degré interne de .
Si est appelé une source.
Si est appelé un puits.
est sans circuit.
Le codage machine employé consiste en une liste de successeurs pour chaque sommet.
Début: Pour tout faire
Pour tout faire
Pour tout faire
Source
Nbsommets
Pour tout faire
Si alors Source Source .
Tant que Source faire
choix(Source)
Source Source privé de
Nbsommets Nbsommets
Pour chaque successeur de faire
Si alors
Source Source .
Si (Nbsommets) alors est sans circuit sinon a au moins un circuit.
Source peut être implémentée sous forme de liste, avec pour fonction de choix la fonction simplissime qui choisit le premier élément.
Pour tout calculer (comme dans l'algorithme précédent)
Pour tout faire:
si alors
Tri-topo( )
Si alors écrire sinon
Pour tout faire
(concaténation)
Pour tout faire
Si alors
Tri-topo( )
Pour tout faire
privé de
Il existe des algorithmes de complexité (beaucoup plus compliqués).
est le nombre de tri topologiques, le nombre de sommets, le nombre d'arcs.
Calculer les degrés internes.
nb-sommets=0
Pour tout faire
Si faire
ajouter() au niveau 0.
nb-sommets++
Tant que niveau() est non vide faire
Pour tout dans niveau() faire
pour tout successeur de faire
Si alors
niveau() niveau()
nb-sommets nb-sommets
La complexité est en .
Soit un graphe orienté, la fermeture transitive de est définie par si et seulement si il existe un chemin de avec et .
Soit un graphe orienté avec et .
Soit un chemin de , l'intérieur de , noté , est . si et seulement si .
On définit une suite de graphes de la manière suivante: si et seulement si il existe un chemin entre et avec . En particulier , et .
( on initialise la matrice avec le graphe)
Pour variant de à faire
Pour variant de à faire
Pour variant de à faire
Pour variant de à faire
La réduction transitive n'est pas toujours unique.
Si est un graphe orienté sans circuit, il a une unique réduction transitive appelé graphe de Hasse.
Pour faire
marque() faux
Pour tout faire
file
tant que file faire
premier(file)
supprimer (,file)
Pour tout faire
Si marque()faux alors
marque() vrai
marque( )
file file { z }
Pour tout faire
marque()
L'algorithme employé est l'algorithme de Goralcicova-Koubek.
marque() faux
On classe les points dans l'ordre d'un tri topologique
Pour variant de à faire
Tant que
Si non(marque(X)) alors
(cas où n'est pas un arc de transitivité)
marque() vrai
Pour tout faire
si non(marque()) alors
marque() vrai
Pour tout faire
marque() faux
suivant: Index monter: aaw précédent: aaw IndexC_antonini,J-F_Quint,P_Borgnat,J_Bérard,E_Lebeau,E_Souche,A_Chateau,O_Teytaud
Source : http://www.les-mathematiques.net/a/a/w/node1.php3#556
11:58 Publié dans Graphes | Lien permanent | Commentaires (0) | | del.icio.us | | Digg | Facebook