Τοπολογική ταξινόμηση: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Αντικατάσταση της σελίδας με 'Κατηγορία:Αλγόριθμοι γράφων Κατηγορία:Αλγόριθμοι ταξινόμησης' |
μ Αναστροφή της επεξεργασίας από τον 194.63.239.232 (συνεισφ.), επιστροφή στην τελευταία εκδοχή υπό [[Χρ... |
||
Γραμμή 1:
{{Πηγές|11|03|2010}}
'''Τοπολογική ταξινόμηση''' ή αλλιώς '''τοπολογική διάταξη''' ([[αγγλικά]]: ''Topological sorting'') ενός [[Κατευθυνόμενος Άκυκλος Γράφος|Κατευθυνόμενου Άκυκλου Γράφου]] (Directed Acyclic Graph ή DAG), ονομάζεται στη [[Θεωρία Γράφων]] η γραμμική διάταξη των κόμβων, έτσι ώστε κάθε πρόγονος ενός [[Κόμβος (θεωρία γράφων)|κόμβου]] v προηγείται του v στη διάταξη. Κάθε Κατευθυνόμενος Άκυκλος Γράφος μπορεί να έχει μία ή περισσότερες τοπολογικές διατάξεις.
Πιο αυστηρά, μπορούμε να ορίσουμε την τοπολογική ταξινόμηση ενός Κατευθυνόμενου Άκυκλου Γράφου G(V, E), με V το σύνολο των κόμβων και E το σύνολο των [[Ακμή (θεωρία γράφων)|ακμών]] ως μία γραμμική αλληλουχία των κόμβων V, έτσι ώστε αν (u, v) <math>\in</math> E, π(u) < π(v), όπου π(x) η θέση στην οποία βρίσκεται ο κόμβος x στη διάταξη.
[[Κατηγορία:Αλγόριθμοι γράφων]]
[[Κατηγορία:Αλγόριθμοι ταξινόμησης]]
{{Αλγόριθμος-επέκταση}}
{{Link FA|de}}
| |||