Τοπολογική ταξινόμηση
μία διάταξη των κόμβων ενός κατευθυνόμενου άκυκλου γράφου, ώστε κάθε ακμή πηγαίνει από νωρίτερο σε αργότερο κόμβο
Στην θεωρία γράφων, τοπολογική ταξινόμηση (ή αλλιώς τοπολογική διάταξη) ενός κατευθυνόμενου ακυκλου γράφου, ονομάζεται η γραμμική διάταξη των κόμβων, έτσι ώστε για κάθε ακμή ο του στη διάταξη. Κάθε κατευθυνόμενος άκυκλος γράφος μπορεί να έχει μία ή περισσότερες τοπολογικές διατάξεις.[1]:612-615[2]:339-342
Η τοπολογική διάταξη μας επιτρέπει να εκτελέσουμε μία σειρά από αλληλεξαρτώμενες εργασίες με μία γραμμική σειρά, ώστε όταν είναι να εκτελεστεί μία εργασία να έχουν ήδη ολοκληρωθεί αυτές από τις οποίες εξαρτάται.
Μαθηματικός ορισμός Επεξεργασία
Έστω ένας κατευθυνόμενος άκυκλος γράφος , όπου είναι το σύνολο των κόμβων του και είναι το σύνολο των ακμών του. Τότε, η μετάθεση των κόμβων του είναι τοπολογική διάταξη ανν
- .
Δείτε επίσης Επεξεργασία
Παραπομπές Επεξεργασία
- ↑ Cormen, Thomas H.· Leiserson, Charles Eric· Rivest, Ronald Linn· Stein, Clifford. Introduction to algorithms (3η έκδοση). Cambridge, Massachusetts London, England: MIT Press. ISBN 9780262033848.
- ↑ Τσίχλας, Κωνσταντίνος· Γούναρης, Αναστάσιος· Μανωλόπουλος, Ιωάννης. Σχεδίαση και ανάλυση αλγορίθμων.
 |
Αυτό το μαθηματικό λήμμα χρειάζεται επέκταση. Μπορείτε να βοηθήσετε την Βικιπαίδεια επεκτείνοντάς το. |