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

Στην θεωρία γράφων, τοπολογική ταξινόμηση (ή αλλιώς τοπολογική διάταξη) ενός κατευθυνόμενου ακυκλου γράφου, ονομάζεται η γραμμική διάταξη των κόμβων, έτσι ώστε για κάθε ακμή $(u,v)$ ο $u$ του $v$ στη διάταξη. Κάθε κατευθυνόμενος άκυκλος γράφος μπορεί να έχει μία ή περισσότερες τοπολογικές διατάξεις.

Στον παραπάνω κατευθυνόμενος άκυκλος γράφο, μία πιθανή τοπολογική ταξινόμηση είναι η $\pi =(6,8,1,2,4,3,5,7)$.

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

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

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

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

Δείτε επίσης

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