Η πρώτη αναφορά στη θεωρία γράφων χρονολογείται από το 1736 και από τον L.Euler στο γνωστό πρόβλημα των γεφυρών του ποταμού Pregel της Ρωσίας.
L.Euler
Όμως το ενδιαφέρον για τα γραφοθεωρητικά μοντέλα παραμένει αυξημένο ως σήμερα, μιας και έχουν δυνατότητες εφαρμογής σε πολλά γνωστικά πεδία και ιδιαιτέρως στην επιστήμη των υπολογιστών.
Αυτό που έχει ιδιαίτερη σημασία για την διαδικασία της  ανάλυσης και επίλυσης ενός προβλήματος στην επιστήμη των υπολογιστών είναι η Μοντελοποίηση του. Δηλαδή η μαθηματικοποίηση της αναπαράστασης και η αντιστοιχία της σε ένα μαθηματικό σύστημα από αντικείμενα και συναρτήσεις. 
Ο προσδιορισμός ενός μοντέλου στο πρόβλημα δεν είναι τίποτα άλλο από μια συγκεκριμένη μαθηματική αναπαράσταση, που η επίλυση της θα αποτελεί και επίλυση του προβλήματος. Μάλιστα, όταν  η αναπαράσταση αυτή περιέχει γράφους τότε θα μιλάμε για γραφοθεωρητικό μοντέλο.
Για παράδειγμα, κατά την ανάλυση ενός προβλήματος Τεχνητής Νοημοσύνης, πολλές φορές υπάρχει η ανάγκη για αναπαράσταση του χώρου καταστάσεων του προβλήματος. 
Ως χώρος καταστάσεων θεωρείται  το σύνολο όλων των έγκυρων καταστάσεων δηλαδή όλων εκείνων των στιγμιότυπων του προβλήματος που είναι αποδεκτά και σύμφωνα με τους περιορισμούς και τις υποθέσεις του προβλήματος. 
Η αναπαράσταση του χώρου, σχηματίζει ένα γράφο στο οποίο οι κόμβοι ή κορυφές, είναι οι καταστάσεις και οι σύνδεσμοι ή ακμές μεταξύ των κόμβων είναι οι ενέργειες ή ιδιότητες που εφαρμόζονται. Η εύρεση της λύσης επιτυγχάνεται με αναζήτηση μέσα στον χώρο καταστάσεων.
Μπορούμε λοιπόν  να δώσουμε τον ορισμό του γράφου.
«  Ένας γράφος G είναι ένα διατεταγμένο ζεύγος , 

G=<V(G),E(E)>όπου :
G=<V(G),E(E)>όπου :
·      V(G)={u1 , u2 ,u3 ...un }είναι το σύνολο κορυφών του G και
·      E(G)={e1 , e2 ,e3 ...en }είναι το σύνολο ακμών του G.
Κάθε ακμή είναι ένα διμελές σύνολο το οποίο αποτελείται από δύο (όχι απαραίτητα διαφορετικές μεταξύ τους ) κορυφές, οι οποίες καλούνται τερματικά σημεία της ακμής»
Κάθε λοιπόν γράφος που ορίζεται από τον παραπάνω ορισμό θα τον λέμε μη-κατευθυνόμενο. Την ακμή αυτού του γράφου θα την συμβολίζουμε με e={u,v} και θα λέμε ότι η ακμή ενώνει τους κόμβους u και v .

Ένας γράφος εκτός από μη- κατευθυνόμενος μπορεί  να είναι κατευθυνόμενος. Τότε η ακμή του θα συμβολίζεται < u,v >  και θα λέμε ότι η κορυφή  v είναι η ουρά ενώ η κορυφή  u είναι η κεφαλή. Για να εκφράσουμε αυτή την σχέση συνήθως την απεικονίζουμε με 
Θα πρέπει όμως να πούμε ότι σε έναν κατευθυνόμενο γράφο αντιστοιχεί ένας μοναδικός μη-κατευθυνόμενος, το αντίστροφο δεν ισχύει. 
Γίνεται κατανοητό ότι σε έναν μη-κατευθυνόμενο αντιστοιχούν
 κατευθυνόμενοι γράφοι, αφού μπορούμε να θεωρήσουμε ότι οι ακμές του
μη-κατευθυνόμενου έχουν δύο διευθύνσεις κατεύθυνσης.


μη-κατευθυνόμενος γράφος
κατευθυνόμενος γράφος








Όπως ήδη αναφέραμε οι γράφοι μπορεί να είναι κατευθυνόμενοι και μη-κατευθυνόμενοι. Στην συνέχεια όταν αναφερόμαστε σε γράφο θα θεωρούμε ότι πρόκειται για μη-κατευθυνόμενους γράφους.

 Δίνουμε τον παρακάτω ορισμό
«Ένα γράφημα G δίχως ανακυκλώσεις και παράλληλες ακμές καλείται απλό γράφημα(simple graph)» 
Ένα απλό γράφημα δεν μπορεί να έχει ανακυκλώσεις και παράλληλες ακμές.
Μια ανακύκλωση(loop)δεν είναι τίποτα άλλο από μια ακμή που ξεκινά και εφάπτεται στην ίδια κορυφή, ενώ αν υπάρχουν περισσότερες από μια ακμές που συνδέουν δύο συγκεκριμένες κορυφές τότε οι ακμές αυτές ονομάζονται παράλληλες.