Ορισμοί

Ένας γράφος (graph) είναι ένα σύνολο από κόμβους που ενώνονται με ακμές.
Ο γράφος ορίζεται πλήρως από τους κόμβους και τη συνδεσμολογία τους.
Αν οι ακμές είναι προσανατολισμένες (ορίζονται δηλαδή από διατεταγμένα ζεύγη κόμβων) τότε ο γράφος λέγεται κατευθυνόμενος (directed).
Αν οι ακμές δεν είναι προσανατολισμένες (ορίζονται δηλαδή από μη διατεταγμένα ζεύγη κόμβων) τότε ο γράφος λέγεται μη κατευθυνόμενος (undirected).
Αν οι ακμές είναι συνδεδεμένς με κάποια αξία (βάρος) τότε ο γράφος λέγεται σταθμισμένος (weighted).
Πλήρης (Complete) ορίζεται ο μη κατευθυνόμενος γράφος που περιέχει ακμές που ενώνουν κάθε ζεύγος κόμβων.
Αραιός καλείται ο γράφος που περιέχει λίγες σχετικά ακμές (λ.χ. για ν κόμβους ο αριθμός των ακμών < ν log ν).
Πυκνός (Dense) καλείται ο γράφος από τον οποίο απουσιάζουν λίγες σχετικά ακμές.