Τοπολογική ταξινόμηση
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
 |
Αυτό το λήμμα ή η ενότητα δεν αναφέρει τις πηγές του ή δεν περιέχει επαρκείς παραπομπές. Μπορείτε να βοηθήσετε την Βικιπαίδεια προσθέτοντας κατάλληλες πηγές και παραπομπές που να υποστηρίζουν το λήμμα. Η σήμανση τοποθετήθηκε στις 11/03/2010. |
Τοπολογική ταξινόμηση ή αλλιώς τοπολογική διάταξη (αγγλικά: Topological sorting) ενός Κατευθυνόμενου Άκυκλου Γράφου (Directed Acyclic Graph ή DAG), ονομάζεται στη Θεωρία Γράφων η γραμμική διάταξη των κόμβων, έτσι ώστε κάθε πρόγονος ενός κόμβου v προηγείται του v στη διάταξη. Κάθε Κατευθυνόμενος Άκυκλος Γράφος μπορεί να έχει μία ή περισσότερες τοπολογικές διατάξεις.
Πιο αυστηρά, μπορούμε να ορίσουμε την τοπολογική ταξινόμηση ενός Κατευθυνόμενου Άκυκλου Γράφου G(V, E), με V το σύνολο των κόμβων και E το σύνολο των ακμών ως μία γραμμική αλληλουχία των κόμβων V, έτσι ώστε αν (u, v) 
E, π(u) < π(v), όπου π(x) η θέση στην οποία βρίσκεται ο κόμβος x στη διάταξη.
 |
Αυτό το λήμμα που σχετίζεται με έναν Αλγόριθμο χρειάζεται επέκταση. Βοηθήστε τη Βικιπαίδεια επεκτείνοντάς το!. |
