Πρόσθετοι ορισμοί

Διαδρομή (path) καλείται μια διάταξη κόμβων οι οποίοι ενώνονται με ακμές.
Απλή διαδρομή (simple path) καλείται η παραπάνω διάταξη όταν κάθε κόμβος εμφανίζεται μια μόνο φορά.
Κύκλος (cycle) καλείται η διαδρομή δύο ή περισσοτέρων κόμβων που καταλήγει στον κόμβο αρχής.
Απόσταση (distance) μεταξύ δύο κόμβων καλείται το μήκος της συντομότερης διαδρομής που τους ενώνει.
Διαδρομή Euler (Euler path) καλείται η διαδρομή ή οποία περνάει από όλες τις ακμές του γράφου ακριβώς μια φορά.
Διαδρομή Hamilton (Hamilton path) καλείται η διαδρομή ή οποία περνάει από όλους τους κόμβους του γράφου ακριβώς μια φορά.
Γράφοι που περιέχουν τις παραπάνω διαδρομές ονομάζονται αντίστοιχα.
Συνεκτικός (connected) ονομάζεται ο γράφος για τον οποίο υπάρχει διαδρομή από κάθε κόμβο σε κάθε άλλο κόμβο.
Βαθμός ενός κόμβου σε έναν μη κατευθυνόμενο γράφο καλείται ο αριθμός των συνδεδεμένων με αυτόν ακμών.
Βαθμός εισόδου (in-degree) σε έναν κατευθυνόμενο γράφο καλείται ο αριθμός των ακμών που καταλήγουν σε αυτόν.
Βαθμός εξόδου (out-degree) σε έναν κατευθυνόμενο γράφο καλείται ο αριθμός των ακμών που ξεκινούν από αυτόν.
Υπογράφος (subgraph) Β ενός γράφου Α καλείται ο γράφος του οποίου όλες οι ακμές και οι κόμβοι περιέχονται στον Α.
Δένδρο σκελετός (spanning tree) ενός γράφου καλείται ο υπογράφος που περιέχει όλους του κόμβους αλλά μόνο όσες ακμές απαιτούνται για να σχηματιστεί δένδρο.