ΒΑΣΙΚΟΙ ΟΡΙΣΜΟΙ ΓΡΑΦΗΜΑΤΩΝ
Γράφημα είναι ένα σύνολο κορυφών(vertices) και ένα σύνολο ακμών(edges) τέτοιο ώστε δύο διακεκριμένες κορυφές να συνδέονται με το πολύ μία ακμή και κάθε ακμή να ενώνει δύο διακεκριμένες κορυφές.
Ψευδογράφημα G είναι μια γενίκευση της έννοιας του γραφήματος.Ορίζεται ψευδογράφημα ένα σύνολο κορυφών και ένα σύνολο ακμών τέτοιο ώστε κάθε ακμή συνδέει μία κορυφή με μία κορυφή.Σε ένα ψευδογράφημα  μπορεί να υπάρχουν πολλαπλές συνδέσεις ή και βρόγχοι.
Πολλαπλές συνδέσεις(multiple connections) έχω όταν υπάρχουν κορυφές που ενώνονται με περισσότερες από μία ακμές.
Βρόγχος (Loop) ονομάζεται η ακμη που να συνδέει μια κορυφή με τον εαυτό της.
Μαθηματικές εκφράσεις γραφήματος
Προσαρτημένος πίνακας (incidence matrix) είναι η μαθηματική έκφραση ενός γραφήματος.Προσαρτημένος πίνακας ενός ψευδογραφήματος είναι ένας m * n πίνακας με m γραμμές που αντιστοιχούν στις κορυφές του ψευδογραφήματος και n στήλες που αντιστοιχούν στις ακμές του.Τα στοιχεία του πίνακα μπορεί να είναι 0 ή 1.Συγκεκριμένα  το στοιχείο στη θέση (i,j) είναι 1 αν η κορυφή ui ανήκει στην ακμή ej και 0 αν δεν ανήκει.
Προσκείμενος πίνακας (adjacency matrix) ενός ψευδογραφήματος είναι ένας m*m πίνακας ο οποίος έχει σαν γραμμές και στήλες τις κορυφές του ψευδογραφήματος.Το στοιχείο στη θέση (i,j) δείχνει το πλήθος των ακμών που συνδέουν την κορυφή ui με την κορυφή uj και αν δεν είναι μηδέν τότε λέμε ότι τα ui , uj είναι παρακείμενα(adjacent).Αν δύο κορυφές δεν ενώνονται τότε βάζουμε 0 ενώ αν όλα τα στοιχεία της γραμμής i είναι μηδέν συμπεραίνουμε ότι η κορυφή ui είναι απομονωμένη (isolated).Αν ο προσκείμενος πίνακας υψωθεί σε μια δύναμη ν τότε το στοιχείο (i,j) του νέου πίνακα είναι ο αριθμός των διαδρομών μήκους ν από την κορυφή ui στην κορυφή uj .
Πλήρες γράφημα των n κορυφών(complete graph of n vertices) -n θετικός ακέραιος- είναι ένα γράφημα που έχει ακριβώς μια ακμή που συνδέει κάθε ζεύγος διακεκριμένων κορυφών.Κατα συνέπεια ο προσκείμενός του πίνακας είναι ένας n*n πίνακας με όλα τα στοιχεία της κύριας διαγωνίυ μηδέν και όλα τα άλλα στοιχέια μονάδα.
Πλήρες διμερές γράφημα στα m και n σημεία Κm,n είναι ένα γράφημα που έχει m+n κορυφές χωρισμένες σε δύο ομάδες,μία με m κορυφές και μία με n.Κάθε κορυφή της μιάς ομάδας ενώνεται με όλες τις κορυφές της άλλης ομάδας αλλά ποτέ με κορυφές της δικής της ομάδας.
Διαδρομή από την κορυφή u στην κορυφή w ενός ψευδογραφήματος ορίζεται η ακολουθία των διαδοχικών ακμών που ακολουθούμε για να πάμε από την κορυφή u στην κορυφή w.Δεν υπάρχουν περιορισμοί στη διαδικασία διαγραφής μιας διαδρομής,δηλαδή μπορεί κανείς να ξαναπεράσει μια ακμή πολλές φορές και κατά οποιαδήποτε κατεύθυνση.
Μήκος μιας διαδρομής είναι ο συνολικός αριθμός των ακμών της.
Απόσταση μεταξύ δύο κορυφών είναι το μήκος της συντομότερης διαδρομής που υπήρχε μεταξύ τους.
Συνεκτικό(connected) είναι ένα ψευδογράφημα αν κάθε ζεύγος διακεκριμένων κορυφών του μπορεί να συνδεθεί με μια διαδρομή.
Κλειστή διαδρομή είναι η διαδρομή που αρχίζει και τελειώνει στην ίδια κορυφή.
Κύκλωμα είναι μια διαδρομή ειδικής μορφής που ικανοποιεί τις ακόλουθες δύο συνθήκες:     1)Είναι κλειστή διαδρομή2)Καμιά ακμή δεν επαναλαμβάνεται.
Απλό κύκλωμα είναι ένα κύκλωμα στο οποίο καμία κορυφή δεν επαναλαμβάνεται.
Υποψευδογράφημα Η ενός ψευδογραφήματος G είναι ένα υποσύνολο κορυφών και ακμών του G τέτοιο ώστε το Η να είναι ένα ψευδογράφημα και όλες οι δευτερεύουσες σχέσεις του Η να είναι επίσης δευτερεύουσες σχέσεις στο G.Το κενό σύνολο είναι ένα παράδειγμα υποψευδογραφήματος του G.
Διμερή γραφήματα είναι τα υπογραφήματα του Κm,n.
Συντελεστής ενός ψευδογραφήματος είναι το μεγαλύτερο συνεκτικό υποψευδογράφημα.
Βαθμός (degree) μιας κορυφής σε ένα ψευδογράφημα είναι το πλήθος των άκρων των ακμών που καταλήγουν σε αυτή.Έτσι οι βρόγχοι αυξάνουν κατά δύο το βαθμό αφού υπολογίζονται δύο άκρα.