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

Ένα παράδειγμα ενός κατευθυνόμενου άκυκλου γράφου.

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

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

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

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

Υπάρχει αλγόριθμος που βρίσκει την τοπολογική ταξινόμηση σε χρόνο $O(n+m)$, όπου $n$ είναι το πλήθος των κόμβων και $m$ το πλήθος των ακμών.

Αλγοριθμικά προβλήματα

Για αρκετά υπολογιστικά προβλήματα, υπάρχουν αποδοτικοί αλγόριθμοι για κατευθυνόμενους άκυκλους γράφους, ενώ για γενικούς γράφους μόνο λιγότερο αποδοτικοί αλγόριθμοι είναι γνωστοί. Για παράδειγμα, το συντομότερο μονοπάτι μπορεί να βρεθεί σε $O(n+m)$ χρόνο, ενώ σε γενικούς γράφους ο αλγόριθμος του Ντάικστρα είναι πιο αργός. Αντίστοιχα, το πρόβλημα της εύρεσης του μακρύτερου μονοπατιού μπορεί να βρεθεί σε $O(n+m)$ χρόνο, ενώ στην γενική περίπτωση είναι NP-Hard πρόβλημα.

Δείτε επίσης

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