Version imprimable
Bonsoir a vous
Voila je cherche des explications sur l'ordre topologique dans un graphe avec cycle, orienté, je ne comprends pas trop a quoi il sert.:oops:
Permet-il de créer un nouveau graphe qui à partir d'un sommet donné, va creer un nouveau graphe avec tous les chemins accessibles a partir de ce sommet?
Si non, existe t il un algo permettant de réaliser ceci?
Merci d'avance pour votre aide
A priori, on n'a d'ordre topologique que si le graphe n'a pas de cycle...
Pour définir un tel ordre (tri topologique), tu peux regarder ce lien.
Ca sert par exemple à ordonnancer des tâche en respectant des dépendances.
Bonjour,
Exact ! On ne parle de tri topologique d'un graphe que si ce dernier ne contient aucun circuit.
On parle aussi de niveau de génération ou rang d'un nœud qui consiste à numéroter les sommets tel que le numéro affecté à chaque sommet est inférieur à celui du suivant et supérieur à celui du précédent.
Le niveau de génération d'un nœud xi est le nombre d'arcs du chemin le plus long qui mène à xi.
Pour réaliser le tri topologique d'un tel graphe, essaie de construite le dictionnaire des précédents, ça te donnera une idée !
Cordialement,
Sidahmed