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

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

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

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

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

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

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

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

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

Για αρκετά υπολογιστικά προβλήματα, υπάρχουν αποδοτικοί αλγόριθμοι για κατευθυνόμενους άκυκλους γράφους, ενώ για γενικούς γράφους μόνο λιγότερο αποδοτικοί αλγόριθμοι είναι γνωστοί. Για παράδειγμα, το συντομότερο μονοπάτι μπορεί να βρεθεί σε ${\displaystyle O(n+m)}$ χρόνο, ενώ σε γενικούς γράφους ο αλγόριθμος του Ντάικστρα είναι πιο αργός. Αντίστοιχα, το πρόβλημα της εύρεσης του μακρύτερου μονοπατιού μπορεί να βρεθεί σε ${\displaystyle O(n+m)}$ χρόνο,^[1]: 404 ενώ στην γενική περίπτωση είναι NP-Hard πρόβλημα.^[1]: 1048

Δείτε επίσης

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

Παραπομπές

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