Discussion :

[BatuBou]

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.
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

[fremen167]

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.

[sidahmed]

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