Τοπολογική ταξινόμηση

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

Τοπολογική ταξινόμηση ή αλλιώς τοπολογική διάταξη (αγγλικά: Topological sorting) ενός Κατευθυνόμενου Άκυκλου Γράφου (Directed Acyclic Graph ή DAG), ονομάζεται στη Θεωρία Γράφων η γραμμική διάταξη των κόμβων, έτσι ώστε κάθε πρόγονος ενός κόμβου v προηγείται του v στη διάταξη. Κάθε Κατευθυνόμενος Άκυκλος Γράφος μπορεί να έχει μία ή περισσότερες τοπολογικές διατάξεις.

Πιο αυστηρά, μπορούμε να ορίσουμε την τοπολογική ταξινόμηση ενός Κατευθυνόμενου Άκυκλου Γράφου G(V, E), με V το σύνολο των κόμβων και E το σύνολο των ακμών ως μία γραμμική αλληλουχία των κόμβων V, έτσι ώστε αν (u, v) \in E, π(u) < π(v), όπου π(x) η θέση στην οποία βρίσκεται ο κόμβος x στη διάταξη.