Μετάβαση στο περιεχόμενο

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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Στον παραπάνω κατευθυνόμενος άκυκλος γράφο, μία πιθανή τοπολογική ταξινόμηση είναι η .

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

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

Μαθηματικός ορισμός

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

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

.
  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. Τσίχλας, Κωνσταντίνος· Γούναρης, Αναστάσιος· Μανωλόπουλος, Ιωάννης. Σχεδίαση και ανάλυση αλγορίθμων.