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

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

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

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

Κάθε κατευθυνόμενος άκυκλος γράφος έχει μια τοπολογική ταξινόμηση κι αυτό συμβαίνει επειδή αυτό το είδος γραφημάτων δεν έχει κύκλους. Η τοπολογική ταξινόμηση ενός κατευθυνόμενου άκυκλου γράφου (δηλαδή με n κορυφές) γίνεται γραμμικά στο μέγεθος του γράφου.

Ευρεση συντομότερων διαδρομών από κοινή αφετηρία 

Θεωρία γράφων