Γράφος

Ένας γράφος με έξι κόμβους και εφτά ακμές.

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

Οι ακμές μπορούν να είναι κατευθυνόμενες (ασύμμετρες) ή μη-κατευθυνόμενες (συμμετρικές). Για παράδειγμα, εάν οι κορυφές αντιπροσωπεύουν τα άτομα σε ένα πάρτι, και υπάρχει ακμή μεταξύ δύο ανθρώπων, αν δίνουν τα χέρια, τότε αυτό είναι ένα μη-κατευθυνόμενο γράφημα, γιατί αν το πρόσωπο Α έδωσε τα χέρια με το πρόσωπο Β, τότε και το πρόσωπο Β έδωσε τα χέρια και με πρόσωπο Α. Από την άλλη πλευρά, εάν οι κορυφές αντιπροσωπεύουν τα άτομα σε ένα πάρτι και υπάρχει μια ακμή από το πρόσωπο Α στο πρόσωπο Β όταν το πρόσωπο Α γνωρίζει το πρόσωπο Β, τότε η γραφική αυτή παράσταση είναι κατευθυνόμενη γιατί το να γνωρίζεις κάποιον δεν είναι απαραίτητα μια συμμετρική σχέση (δηλαδή, ένα άτομο που γνωρίζει ένα άλλο πρόσωπο δεν συνεπάγεται κατ 'ανάγκη το αντίθετο, για παράδειγμα, πολλοί άνθρωποι μπορεί να γνωρίζουν μια διάσημη προσωπικότητα αλλά η διάσημη προσωπικότητα είναι απίθανο να γνωρίζει όλους τους οπαδούς της). Το τελευταίο αυτό είδος γραφήματος ονομάζεται κατευθυνόμενο γράφημα και οι ακμές του ονομάζονται κατευθυνόμενες ακμές ή τόξα.

Οι κορυφές καλούνται επίσης κόμβοι ή σημεία, και οι ακμές ονομάζονται επίσης γραμμές. Τα γραφήματα είναι το βασικό θέμα μελέτης από τη θεωρία γραφημάτων. Η λέξη «γράφημα» χρησιμοποιήθηκε για πρώτη φορά με αυτή την έννοια από τον James Joseph Sylvester το 1878.

Ορισμοί

Οι ορισμοί στην θεωρία γραφημάτων διαφέρουν. Οι παρακάτω είναι μερικοί από τους πιο βασικούς τρόπους ορισμού των γραφημάτων και των σχετικών μαθηματικών δομών.

Γράφημα

Στην πιο κοινή έννοια του όρου, ένα γράφημα είναι ένα διατεταγμένο ζεύγος G = (V, E) αποτελούμενο από ένα σύνολο V των κορυφών ή κόμβων μαζί με E σύνολο από ακμές ή γραμμές, οι οποίες είναι υποσύνολα δύο στοιχείων V (δηλαδή, μια ακμή σχετίζεται με δύο κορυφές και η σχέση απεικονίζεται ως μη ταξινομημένο ζεύγος των κορυφών σε σχέση με τη συγκεκριμένη ακμή). Για να αποφευχθούν οι αμφισημίες, αυτός ο τύπος γραφήματος μπορεί να περιγραφεί με ακρίβεια ως μη-κατευθυνόμενο και απλό.

Άλλες έννοιες του γραφήματος προέρχονται από διαφορετικές αντιλήψεις για το σύνολο των ακμών του. Σε μια πιο γενικευμένη έννοια, E είναι ένα σύνολο το οποίο σχετίζεται με τη σχέση της συχνότητας με την οποία συνδέονται δύο κορυφές με κάθε ακμή. Σε μια άλλη γενικευμένη έννοια, E είναι ένα πολυσύνολο από μη ταξινομημένα ζεύγη κορυφών (όχι κατ 'ανάγκη διαφορετικά μεταξύ τους). Πολλοί συγγραφείς ονομάζουν αυτό το είδος αντικειμένων πολύγραφο ή ψευδογράφημα.

Οι κορυφές που ανήκουν σε μια ακμή ονομάζονται τελικά σημεία ή τελικές κορυφές της ακμής. Μια κορυφή μπορεί να υπάρχει σε ένα γράφημα και να μην ανήκει σε ακμή. V και Ε συνήθως λαμβάνονται υπόψιν για ένα πεπερασμένο σύνολο, και πολλά από τα γνωστά αποτελέσματα δεν είναι αληθινά (ή είναι αρκετά διαφορετικά) για άπειρα γραφήματα, επειδή πολλά από τα επιχειρήματα αποτυγχάνουν σε άπειρες καταστάσεις. Η σειρά ενός γραφήματος είναι $|V|$ (ο αριθμός των κορυφών). Το μέγεθος ενός γραφήματος είναι $|E|$, ο αριθμός των ακμών. Ο βαθμός ενός κόμβου είναι ο αριθμός των ακμών που συνδέονται με αυτόν, όπου μια ακμή η οποία συνδέεται με την κορυφή και στα δύο άκρα (ένας βρόχος) συνυπολογίζεται δύο φορές. Για μια ακμή {u, v}, οι θεωρητικοί των γραφημάτων συνήθως χρησιμοποιούν την μικρότερη σημειογραφία uv.

Σχέση γειτνίασης

Οι ακμές Ε ενός μη-κατευθυνόμενου γραφήματος G περικλείουν μια συμμετρική δυαδική σχέση ~ με την V η οποία ονομάζεται σχέση γειτνίασης του G. Συγκεκριμένα, για κάθε ακμή {u, v}, οι κορυφές u και v λέγεται ότι είναι γειτονικές η μία στην άλλη, κάτι το οποίο συμβολίζεται ως u ~ v.

Συνεκτικότητα και συνιστώσες

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

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

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

Μονοπάτια και είδη

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

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

Τύποι γραφημάτων

Διάκριση όσον αφορά τον κύριο ορισμό

Όπως προαναφέρθηκε, σε διάφορα πλαίσια μπορεί να είναι χρήσιμο να προσδιορισθεί ο όρος γράφημα με διαφορετικούς βαθμούς γενικότητας. Όποτε είναι απαραίτητο να καθορισθεί μια αυστηρή διάκριση, χρησιμοποιούνται οι παρακάτω όροι. Πιο συχνά, στα σύγχρονα κείμενα στην θεωρία γράφων, εκτός αν ορίζεται διαφορετικά, γράφημα σημαίνει "απλό, πεπερασμένο, μη-κατευθυνόμενο γράφημα " (δείτε τους ορισμούς παρακάτω).

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

Ένα μη-κατευθυνόμενο γράφημα είναι εκείνο στο οποίο οι ακμές δεν έχουν προσανατολισμό. Η ακμή (α, β) είναι ταυτόσημη με την άκρη (β, α), δηλαδή, δεν υπάρχουν διατεταγμένα ζεύγη, αλλά σύνολα {u, v} (ή 2-multisets) των κορυφών.

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

Ένα κατευθυνόμενο γράφημα ή διγράφημα είναι ένα διατεταγμένο ζεύγος D = (V, A) όπου V, είναι ένα σύνολο του οποίου τα στοιχεία λέγονται κορυφές ή κόμβοι και Α, είναι μια σειρά από διατεταγμένα ζεύγη κορυφών, τα οποία ονομάζονται τόξα, διατεταγμένες ακμές ή βέλη. Ένα τόξο a = (x, y) θεωρείται ότι κατευθύνεται από το x στο y; y ονομάζεται η αρχή και x to τέλος του τόξου; y λέγεται ότι είναι άμεσος διάδοχος του x, και το x λέγεται ότι είναι ο άμεσος προκάτοχός του y. Αν ένα μονοπάτι οδηγεί από το x στο y, τότε το y λέγεται ότι είναι διάδοχος του x και προσβάσιμο από το x, και το x λέγεται ότι είναι ο προκάτοχος του y. Το τόξο (y, x) ονομάζεται το τόξο (x, y) ανεστραμμένο.

Ένας κατευθυνόμενο γράφημα D λέγεται συμμετρικός αν για κάθε τόξο στο D, το αντίστοιχο αντεστραμμένο τόξο ανήκει και αυτό στο D. Ένα συμμετρικό χωρίς επαναλήψεις κατευθυνόμενο γράφημα D = (V, A) είναι ισοδύναμο με ένα απλό μη-κατευθυνόμενο γράφημα G = (V, E) , όπου τα ζευγάρια του αντιστρόφου τόξου στο Α αντιστοιχούν 1-προς-1 με τις ακμές στο E; έτσι ο αριθμός |E| = |A|/2, ή το μισό του αριθμού των τόξων στο D. Μια παραλλαγή αυτού του ορισμού είναι το προσανατολισμένο γράφημα, στο οποίο δεν μπορούν να υπάρχουν παραπάνω από ένα από τα (x, y) και (y, x) τα οποία μπορούν να είναι τόξα.

Μικτό γράφημα

Ένα μικτό γράφημα G είναι ένα γράφημα στο οποίο μερικές ακμές μπορεί να είναι κατευθυνόμενες και κάποιες μπορεί να είναι μη κατευθυνόμενες. Το γράφημα είναι γραμμένο ως διατεταγμένο τριπλό G = (V, E, A) με V, E και A όπως ορίζεται ανωτέρω. Τα κατευθυνόμενα και μη κατευθυνόμενα γραφήματα είναι ειδικές περιπτώσεις.

Πολύγραφος

Ένας βρόχος είναι μια ακμή (κατευθυνόμενη ή μη), η οποία αρχίζει και τελειώνει στην ίδια κορυφή. Αυτό μπορεί να επιτρέπεται ή να μην επιτρέπεται ανάλογα με την εφαρμογή. Στο πλαίσιο αυτό, μια ακμή με δύο διαφορετικές άκρες ονομάζεται μια σύνδεση. Ο όρος "πολύγραφος» είναι γενικά αποδεκτό ότι εννοεί ότι επιτρέπονται πολλαπλές ακμές (και μερικές φορές βρόχοι). Σε περίπτωση που τα γραφήματα ορίζονται έτσι ώστε να επιτρέπουν loops και πολλαπλές ακμές, ένας πολύγραφος ορίζεται συχνά για να σημαίνει ένα γράφημα χωρίς βρόχους, ωστόσο, όπου τα γραφήματα ορίζονται έτσι ώστε να μην επιτρέπονται loops και πολλαπλές ακμές, ο όρος ορίζεται συχνά για να σημαίνει ένα «γράφημα», το οποίο μπορεί να έχει και πολλές ακμές και βρόχους, αν και πολλοί χρησιμοποιούν τον όρο "pseudograph" για αυτήν την έννοια.

Απλό γράφημα

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

Σταθμισμένο γράφημα

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

Half-edges, loose edges

Σε εξαιρετικές περιπτώσεις είναι απαραίτητο να υπάρχουν ακμές με μόνο το ένα άκρο, οι οποίες ονομάζονται half-edges, ή καθόλου άκρα (loose edges).

Σημαντικές κατηγορίες γραφημάτων

Τυπικό γράφημα

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

Πλήρες γράφημα

Ένα πλήρες γράφημα έχει το χαρακτηριστικό ότι κάθε ζευγάρι κορυφών έχει μια ακμή που να τους συνδέει.

Πεπερασμένα και άπειρα γραφήματα

Ένα πεπερασμένο γράφημα είναι ένα γράφημα G = (V, E) έτσι ώστε V και Ε να είναι πεπερασμένα σύνολα. Ένα άπειρο γράφημα είναι ένα γράφημα με ένα άπειρο σύνολο κορυφών ή ακμών ή και τα δύο. Πολύ συχνά στη θεωρία γραφημάτων υπονοείται ότι τα γραφήματα που συζητώνται είναι πεπερασμένα. Εάν τα γραφήματα είναι άπειρα, αυτό συνήθως αναφέρεται συγκεκριμένα.

Κλάσεις γραφημάτων από πλευράς συνδεσιμότητας

Σε ένα μη-κατευθυνόμενο γράφημα G, δύο κορυφές u και v ονομάζονται συνδεδεμένες αν το G περιέχει μια διαδρομή από το u στο v. Σε αντίθετη περίπτωση, καλούνται μη συνδεδεμένες. Ένα γράφημα ονομάζεται συνδεδεμένο αν κάθε ζεύγος διακριτών κορυφών στο γράφημα είναι συνδεδεμένο. Αλλιώς, το γράφημα ονομάζεται μη συνδεδεμένο.

Ένα γράφημα λέγεται k-vertex-connected ή k-edge-connected αν δεν υπάρχει σύνολο από k-1 κορυφές (αντίστοιχα, ακμές) που όταν αφαιρεθούν να αποσυνδέεται το γράφημα. Ένα k-vertex-connected γράφημα καλείται συχνά απλά ως k-connected. Ένα κατευθυνόμενο γράφημα λέγεται ασθενώς συνδεδεμένο εάν αντικαθιστώντας όλες τις κατευθυνόμενες ακμές του με μη-κατευθυνόμενες ακμές παράγεται ένα συνδεδεμένο (μη-κατευθυνόμενο) γράφημα. Είναι άρρηκτα συνδεδεμένο ή ισχυρό αν περιέχει ένα κατευθυνόμενο μονοπάτι από τον u στον v και ένα κατευθυνόμενο μονοπάτι από τον v με u για κάθε ζεύγος κορυφών u, v.

Ιδιότητες των γραφημάτων

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

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

Σε ένα σταθμισμένο γράφημα ή διγράφημα κάθε άκρο συνδέεται με κάποια αξία, που ονομάζεται ποικιλοτρόπως ως κόστος, βάρος, μήκος ή με κάποιον άλλο όρο ανάλογα με την εφαρμογή. Τέτοιου είδους γραφήματα προκύπτουν σε πολλά πλαίσια, για παράδειγμα στο πρόβλημα βέλτιστης δρομολόγησης.

Σημαντικά γραφήματα

Βασικά παραδείγματα είναι:

• Σε ένα πλήρες γράφημα, κάθε ζεύγος κορυφών είναι ενωμένα μεταξύ τους με μια ακμή. Δηλαδή, το γράφημα περιέχει όλες τις πιθανές ακμές.
• Σε ένα διμερές γράφημα, το σύνολο των κορυφών μπορεί να χωριστεί σε δύο ομάδες, W και X, έτσι ώστε να μην υπάρχουν δύο κορυφές στο W που να είναι γειτονικές και να μην υπάρχουν δύο κορυφές στο Χ που να είναι γειτονικές. Εναλλακτικά, αυτό είναι ένα γράφημα με [Χρωματισμός γραφήματος|χρωματικό αριθμό] 2.
• Σε ένα πλήρες διμερές γράφημα, το σύνολο των κορυφών είναι η ένωση των δύο διακριτών συνόλων, W και X, έτσι ώστε κάθε κορυφή στο σύνολο W να είναι γειτονική με κάθε κορυφή στο σύνολο X αλλά να μην υπάρχουν ακμές ανάμεσα στο W ή X.
• Σε ένα γραμμικό γράφημα ή γράφημα με μονοπάτι μήκους n, οι κορυφές μπορούν να απαριθμούνται κατά σειρά, v₀, v₁, ..., v_n έτσι ώστε οι ακμές να είναι v_i−1v_i για κάθε i = 1, 2, ..., n . Αν ένα γραμμικό γράφημα εμφανίζεται ως υπογράφημα ενός άλλου γραφήματος, αυτό είναι ένα μονοπάτι στο γράφημα.
• Σε ένα κυκλικό γράφημα μήκους n ≥ 3, οι κορυφές μπορούν να ανομαστούν v₁, ..., v_n έτσι ώστε οι ακμές να v_i−1v_i για κάθε i = 2,...,n καθώς και v_nv₁. Τα κυκλικά γραφήματα μπορούν να χαρακτηριστούν ως συνδεδεμένα 2-τακτικά γραφήματα. Εάν ένα κυκλίκό γράφημα εμφανίζεται ως υπογράφημα ενός άλλου γραφήματος τότε αυτό είναι ένας κύκλος ή κύκλωμα σε αυτό το γράφημα.
• Ένα επίπεδο γράφημα είναι ένα γράφημα του οποίου οι κορυφές και οι ακμές μπορούν να εξαχθούν σε ένα επίπεδο τέτοιο, ώστε να μην υπάρχουν δύο ακμές οι οποίες να τέμνονται.
• Ένα δέντρο είναι ένα συνεκτικό γράφημα χωρίς κύκλους.
• Ένα δάσος είναι ένα γράφημα χωρίς κύκλους (δηλ. η ένωση από ένα ή περισσότερα δέντρα).

Μερικά πιο προχωρημένα είδη γραφημάτων είναι:

• Το γράφημα Petersen και γενικεύσεις του
• Τέλεια γραφήματα
• Συγκράφηματα(Cographs)
• Χορδογραφήματα (Chordal graphs)
• Άλλα γραφήματα με μεγάλες ομάδες

Γενικεύσεις

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

Ένα μη-κατευθυνόμενο γράφημα μπορεί να θεωρηθεί ως ένα simplicial complex το οποίο αποτελείται από 1-simplices (τις ακμές) και 0-simplices (τις κορυφές). Ως εκ τούτου, τα complexes είναι γενικεύσεις των γραφημάτων, δεδομένου ότι αφήνουν περιθώρια για simplices μεγαλύτερων διαστάσεων.

Κάθε γράφημα δημιουργεί ένα matroid.

Στη Θεωρία μοντέλων, ένα γράφημα είναι μόνο μια δομή. Στην περίπτωση όμως αυτή, δεν υπάρχει περιορισμός στον αριθμό των ακμών: μπορεί να είναι οποιοσδήποτε απόλυτος αριθμός, βλ. Συνεχές γράφημα.

Στην υπολογιστική βιολογία,η ανάλυση των power graphs παρουσιάζει τα power graphs ως μια εναλλακτική αναπαράσταση των τυχαίων γραφημάτων.

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

Δείτε επίσης

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

Δημοσιεύσεις

• Balakrishnan, V. K. (1997). Graph Theory (1st έκδοση). McGraw-Hill. ISBN 978-0-07-005489-9. 
• Bang-Jensen, J.· Gutin, G. (2000). Digraphs: Theory, Algorithms and Applications. Springer. 
• Bender, Edward A.· Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. 
• Berge, Claude (1958). Théorie des graphes et ses applications (στα Γαλλικά). Paris: Dunod. 
• Biggs, Norman (1993). Algebraic Graph Theory (2nd έκδοση). Cambridge University Press. ISBN 978-0-521-45897-9. 
• Bollobás, Béla (2002). Modern Graph Theory (1st έκδοση). Springer. ISBN 978-0-387-98488-9. 
• Diestel, Reinhard (2005). Graph Theory (3rd έκδοση). Berlin, New York: Springer-Verlag. ISBN 978-3-540-26183-4. 
• Graham, R.L.· Grötschel, M.· Lovász, L. (1995). Handbook of Combinatorics. MIT Press. ISBN 978-0-262-07169-7. 
• Gross, Jonathan L.· Yellen, Jay (1998). Graph Theory and Its Applications. CRC Press. ISBN 978-0-8493-3982-0. 
• Gross, Jonathan L.· Yellen, Jay (2003). Handbook of Graph Theory. CRC. ISBN 978-1-58488-090-5. 
• Harary, Frank (1995). Graph Theory. Addison Wesley Publishing Company. ISBN 978-0-201-41033-4. 
• Iyanaga, Shôkichi· Kawada, Yukiyosi (1977). Encyclopedic Dictionary of Mathematics. MIT Press. ISBN 978-0-262-09016-2. 
• Zwillinger, Daniel (2002). CRC Standard Mathematical Tables and Formulae (31st έκδοση). Chapman & Hall/CRC. ISBN 978-1-58488-291-6.