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

Στην θεωρία γράφων, τοπολογική ταξινόμηση (ή αλλιώς τοπολογική διάταξη) ενός κατευθυνόμενου ακυκλου γράφου, ονομάζεται η γραμμική διάταξη των κόμβων, έτσι ώστε για κάθε ακμή $(u,v)$ ο $u$ του $v$ στη διάταξη. Κάθε κατευθυνόμενος άκυκλος γράφος μπορεί να έχει μία ή περισσότερες τοπολογικές διατάξεις.^[1]^:612-615^[2]^:339-342

Η τοπολογική διάταξη μας επιτρέπει να εκτελέσουμε μία σειρά από αλληλεξαρτώμενες εργασίες με μία γραμμική σειρά, ώστε όταν είναι να εκτελεστεί μία εργασία να έχουν ήδη ολοκληρωθεί αυτές από τις οποίες εξαρτάται.

Μαθηματικός ορισμός[Επεξεργασία | επεξεργασία κώδικα]

Έστω ένας κατευθυνόμενος άκυκλος γράφος $G=(V,E)$ , όπου $V$ είναι το σύνολο των κόμβων του και $E$ είναι το σύνολο των ακμών του. Τότε, η μετάθεση $\pi$ των κόμβων του είναι τοπολογική διάταξη ανν

\forall (u,v)\in E.\pi (u)<\pi (v)

.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Κατευθυνόμενος άκυκλος γράφος

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

↑ Cormen, Thomas H.· Leiserson, Charles Eric· Rivest, Ronald Linn· Stein, Clifford. Introduction to algorithms (3η έκδοση). Cambridge, Massachusetts London, England: MIT Press. ISBN 9780262033848.
↑ Τσίχλας, Κωνσταντίνος· Γούναρης, Αναστάσιος· Μανωλόπουλος, Ιωάννης. Σχεδίαση και ανάλυση αλγορίθμων.

Αυτό το μαθηματικό λήμμα χρειάζεται επέκταση. Μπορείτε να βοηθήσετε την Βικιπαίδεια επεκτείνοντάς το.

[CLRS-1] Cormen, Thomas H.· Leiserson, Charles Eric· Rivest, Ronald Linn· Stein, Clifford. Introduction to algorithms (3η έκδοση). Cambridge, Massachusetts London, England: MIT Press. ISBN 9780262033848.

[2] Τσίχλας, Κωνσταντίνος· Γούναρης, Αναστάσιος· Μανωλόπουλος, Ιωάννης. Σχεδίαση και ανάλυση αλγορίθμων.

[1]

[2]