Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Tri topologique
Résumé
En théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe acyclique orienté (ou dag, de l'anglais directed acyclic graph) est un ordre total sur l'ensemble des sommets, dans lequel s précède t pour tout arc d'un sommet s à un sommet t.
En d'autres termes, un tri topologique est une extension linéaire de l'ordre partiel sur les sommets déterminés par les arcs.
Soit un graphe orienté avec et .
Un ordre topologique sur ce graphe peut donner par exemple la succession des sommets 7, 1, 2, 9, 8, 4, 3, 5, 6. En effet, chaque sommet apparaît bien avant ses successeurs. Il n'y a pas unicité de l'ordre.
Pour un graphe représenté en mémoire sous une forme facile à parcourir, par exemple par listes d'adjacence, le calcul d'un tri topologique est simple. Il suffit d'effectuer un parcours en profondeur du graphe, au cours duquel on empile chaque sommet une fois ses successeurs visités. En désempilant, on obtient un tri topologique.
Sans dédier une procédure pour ce traitement (gros graphes), on peut se re-servir d'un parcours en profondeur déjà effectué pour déterminer directement un ordre topologique. En effet, la lecture des sommets dans l'ordre inverse de la numérotation postfixe du parcours en profondeur est un ordre topologique.
Une autre façon de procéder consiste à rechercher une racine (sommet sans prédécesseur), l'enlever, et répéter l'opération autant de fois que nécessaire. C'est facile si l'on peut facilement calculer le nombre de prédécesseurs d'un sommet ; en effet, les racines à une itération sont parmi les successeurs des racines à l'itération précédente, et un compteur des prédécesseurs permet de les reconnaître.
L'algorithme de tri topologique d'un graphe fonctionne sur le même principe que l'algorithme de parcours en profondeur en rajoutant une notion de date de début et de date de fin. L'ordre topologique sera à la fin les sommets dans l'ordre du tableau de date de fin.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées (2)
Personnes associées (3)
Concepts associés (18)
Tri topologique
En théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe acyclique orienté (ou dag, de l'anglais directed acyclic graph) est un ordre total sur l'ensemble des sommets, dans lequel s précède t pour tout arc d'un sommet s à un sommet t. En d'autres termes, un tri topologique est une extension linéaire de l'ordre partiel sur les sommets déterminés par les arcs. Soit un graphe orienté avec et . Un ordre topologique sur ce graphe peut donner par exemple la succession des sommets 7, 1, 2, 9, 8, 4, 3, 5, 6.
Transitive reduction
In the mathematical field of graph theory, a transitive reduction of a directed graph D is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices v, w a (directed) path from v to w in D exists if and only if such a path exists in the reduction. Transitive reductions were introduced by , who provided tight bounds on the computational complexity of constructing them. More technically, the reduction is a directed graph that has the same reachability relation as D.
Problème de la plus longue chaîne
vignette|Par suppression d'une arête rouge arbitraire, ce cycle hamiltonien donne une chaîne de longueur maximale. En théorie des graphes et en informatique théorique, le problème de la plus longue chaîne (ou le problème du plus long chemin dans le cas d'un graphe orienté) consiste à déterminer la plus longue chaîne élémentaire dans un graphe. Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet. La longueur d'une chaîne peut être mesurée par le nombre d'arêtes qui la composent ou, dans le cas de graphes pondérés, par la somme des poids des arêtes du chemin.
Cours associés (4)
CS-250: Algorithms
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
CS-455: Topics in theoretical computer science
The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of f
CS-448: Sublinear algorithms for big data analysis
In this course we will define rigorous mathematical models for computing on large datasets, cover main algorithmic techniques that have been developed for sublinear (e.g. faster than linear time) data