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

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

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

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

Ένα (ψεύτικο) οδικό δίκτυο.
Οι διασταυρώσεις στο οδικό δίκτυο είναι οι κόμβοι του γράφου
Ο γράφος που αναπαριστά το οδικό δίκτυο.
Το συντομότερο μονοπάτι μεταξύ δύο κορυφών.
Γράφος που αναπαριστά το κοινωνικό δίκτυο μίας παρέας, οι κόμβοι είναι άνθρωποι και οι ακμές υπάρχουν μεταξύ δύο ανθρώπων που είναι φίλοι μεταξύ τους. Εδώ, η Μαρία είναι φίλη με τον Γιώργο και την Δέσποινα, ο Γιώργος με τον Αντώνη, την Μαρία και την Δέσποινα, η Δέσποινα με την Μαρία, τον Γιώργο και την Ελένη, η Ελένη με την Δέσποινα και ο Αντώνης με τον Γιώργο.

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

Αν και οι απαρχές της θεωρίας γράφων θεμελιώθηκαν κατά τον 18ο αιώνα, αναπτύχθηκε μετά τον δεύτερο παγκόσμιο πόλεμο ως ξεχωριστό πεδίο των εφαρμοσμένων μαθηματικών.[1]:vii Ο κλάδος της πληροφορικής ασχολήθηκε με την ανάπτυξη γρήγορων αλγορίθμων (δηλαδή αυτοματοποιημένων διαδικασιών), που επιτρέπουν την επίλυση ορισμένων προβλημάτων σε γράφους, όπως αυτό της εύρεσης του συντομότερου μονοπατιού μεταξύ δύο κόμβων.

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

Γράφος[Επεξεργασία | επεξεργασία κώδικα]

Κύριο λήμμα: Γράφος

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

Μη κατευθυνόμενος γράφος[Επεξεργασία | επεξεργασία κώδικα]

Ένας μη κατευθυνόμενος γράφος είναι ένα διατεταγμένο ζεύγος , όπου[1]: 11 

  • το σύνολο των κόμβων,
  • είναι το σύνολο των ακμών, όπου για κάθε υπάρχουν δύο κόμβοι ώστε .

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

Αναπαράσταση του γράφου του παραδείγματος.

Παράδειγμα[Επεξεργασία | επεξεργασία κώδικα]

Ο γράφος στην δεξιά εικόνα αναπαριστά τον με

  • κόμβους ,
  • ακμές .

Παρατηρήστε ότι με τον ορισμό αυτό η ακμή είναι η ίδια με την ακμή .

Βασικές έννοιες[Επεξεργασία | επεξεργασία κώδικα]

Βαθμός κόμβου[Επεξεργασία | επεξεργασία κώδικα]

Η γειτονιά ενός κόμβου είναι το σύνολο των κόμβων που είναι συνδεδεμένοι με τον μέσω μίας ακμής, δηλαδή

.

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

Στον παραπάνω γράφο, ισχύει ότι και , καθώς και .

Μονοπάτι[Επεξεργασία | επεξεργασία κώδικα]

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

Στον παραπάνω γράφο, η ακολουθία είναι ένα απλό μονοπάτι και η ακολουθία είναι ένα μη-απλό μονοπάτι (καθώς ο κόμβος επαναλαμβάνεται).

Συνεκτικότητα[Επεξεργασία | επεξεργασία κώδικα]

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

Συνεκτικός γράφος
Μη-συνεκτικός γράφος
Μη-συνεκτικός γράφος

Κατευθυνόμενος γράφος[Επεξεργασία | επεξεργασία κώδικα]

Ένας κατευθυνόμενος γράφος είναι ένα διατεταγμένο ζεύγος , όπου:

  • είναι το σύνολο των κορυφών,
  • είναι το σύνολο των ακμών, όπου για κάθε υπάρχουν δύο κόμβοι , ώστε , ώστε .

Εδώ κάθε ακμή είναι ένα διατεταγμένο ζεύγος αποτελούμενο από δύο κορυφές, οι οποίες αποκαλούνται τερματικές κορυφές (κόμβοι) και δεν είναι απαραίτητα διαφορετικές μεταξύ τους. Η διαφορά ανάμεσα σε έναν μη κατευθυνόμενο και έναν κατευθυνόμενο γράφο είναι ότι στην πρώτη περίπτωση έχουμε διμελές σύνολο, ενώ στη δεύτερη διατεταγμένο ζεύγος, δηλαδή για η ακμή έχει την αντίθετη φορά από την .[1]: 13 

Παράδειγμα[Επεξεργασία | επεξεργασία κώδικα]

Αναπαράσταση του κατευθυνόμενου γράφου του παραδείγματος.

Ο γράφος στην δεξιά εικόνα αναπαριστά τον με

  • κόμβους ,
  • ακμές .

Παρατηρήστε ότι η ακμή είναι διαφορετική από την ακμή .

Βασικές έννοιες[Επεξεργασία | επεξεργασία κώδικα]

Βαθμός κόμβου[Επεξεργασία | επεξεργασία κώδικα]

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

Η έσω γειτονιά ενός κόμβου ορίζεται ως το σύνολο των κόμβων με ακμή προς τον , δηλαδή

.

Ο έσω βαθμός του κόμβου ορίζεται ως .

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

.

Ο έξω βαθμός του κόμβου ορίζεται ως .

Για παράδειγμα, για τον κόμβο ισχύει ότι και , και επομένως και .

Μονοπάτι[Επεξεργασία | επεξεργασία κώδικα]

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

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

Συνεκτικότητα[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

Ειδικές κατηγορίες γράφων[Επεξεργασία | επεξεργασία κώδικα]

Πλήρης γράφος με 6 κόμβους, όπου κάθε κόμβος συνδέεται με ακμή με κάθε άλλο κόμβο.
Παράδειγμα δέντρου, δηλαδή μη κατευθυνόμενου γράφου χωρίς κύκλους.
Κύκλος με 7 κόμβους.
Αστεροειδής γράφος με 7 κόμβους.
Γράφος-μονοπάτι με 5 κόμβους.

Επιπλέον, υπάρχουν κάποιες έννοιες στην θεωρία γράφων που δεν είναι αυστηρώς ορισμένες. Για παράδειγμα ένας γράφος με σχετικά λίγες ακμές λέγεται αραιός ενώ αν έχει πολλές ακμές λέγεται πυκνός.[2]

Ιστορία της θεωρίας γράφων[Επεξεργασία | επεξεργασία κώδικα]

Πρόβλημα της γέφυρας της Καίνιξμπεργκ.
Διαδραστική αναπαράσταση του περίπατου του αλόγου σε μία σκακιέρα 5 × 5.

Η εργασία του Λέοναρντ Όιλερ για τις επτά γέφυρες του Καίνιξμπεργκ που δημοσιεύτηκε το 1736, θεωρείται η πρώτη εργασία στην ιστορία της θεωρίας γράφων.[3] Αυτή η εργασία, καθώς επίσης και αυτή του Αλέξιος-Θεόφιλος Βαντερμόντ για το πρόβλημα του περίπατου ενός αλόγου σε μία σκακιέρα, έγιναν χρησιμοποιώντας ανάλυση θέσης (analysis situs) του Λάιμπνιτς. Ο τύπος του Όιλερ, σχετικά με τον αριθμό των ακμών, των κορυφών και των εδρών ενός κυρτού πολυέδρου μελετήθηκε από τον Ωγκυστέν-Λουί Κωσύ[4] και τον Σιμόν Αντουάν Ζαν Λ' Ουιγιέ (Simon Antoine Jean L'Huillier)[5] και θεωρείται ως η αρχή της τοπολογίας.

Σχεδόν εκατό χρόνια μετά την εργασία του Όιλερ και την εισαγωγή της τοπολογίας από τον Γιόχαν Μπένεντικτ Λίστινγκ (Johann Benedict Listing), ο Άρθουρ Κέιλι μελέτησε μια ιδιαίτερη κατηγορία γράφων, τα δέντρα. Η μελέτη αυτών των ιδιαίτερων γράφων είχε πολλές εφαρμογές στη θεωρητική χημεία. Οι τεχνικές που αναπτύχθηκαν είχαν να κάνουν κυρίως με την απαρίθμηση γράφων που παρουσίαζαν κάποιες ιδιαίτερες ιδιότητες.[6] Η απαριθμητική θεωρία γράφων ήταν ένα από τα αποτελέσματα της εργασίας του Κέιλι και δημοσιεύσεων του Τζορτζ Πόλια (George Pólya) μεταξύ του 1935 και 1937. Αυτά γενικεύθηκαν από τον ντε Μπρούιν το 1959. Ο Κέιλι συνέδεσε τα συμπεράσματά του για τα δέντρα με τις σύγχρονες μελέτες για τη χημική σύνθεση.[7] Η σύνθεση των μαθηματικών και των χημικών εννοιών οδήγησαν σε μεγάλο μέρος της σύγχρονης τυπικής ορολογίας της θεωρίας γράφων.

Ο Τζέιμς Τζόσεφ Συλβέστερ εισήγαγε τον όρο "γράφο" σε μία δημοσίευσή του το 1878 στο περιοδικό Nature, όπου κάνει μία αναλογία μεταξύ των "invariants" και των "co-variants" της άλγεβρας και των μοριακών διαγραμμάτων:[8]

"[…] Κάθε invariant και co-variant επομένως μπροεί να εκφραστεί ως ένας γράφος που είναι ακριβώς ο ίδιος με ένα διάγραμμα Kekulé ή έναν χημικογράφο. […] Δίνω έναν κανόνα για τον γεωμετρικό πολλαπλασιασμό των γράφων, δηλαδή για την κατασκευή ενός γράφου για το γινόμενο των in- ή co-variants των οποίων ο γράφος είναι δοσμένος. […]"

Το πρώτο βιβλίο για την θεωρία γράφων γράφτηκε από τον Dénes Kőnig, και δημοσιεύτηκε το 1936.[9] Ένα άλλο βιβλίο από τον Frank Harary, δημοσιεύτηκε το 1969, και "θεωρούταν ως το απόλυτο βιβλίο στο αντικείμενο",[10] και επέτρεψε σε μαθηματικούς, χημικούς, ηλεκτρολόγους μηχανικούς και κοινωνικούς επιστήμονες να μιλάνε μεταξύ τους. Ο Harary δώρισε όλα τα δικαιώματα για να χορηγήσει το Βραβείο Pólya.[11]

Χρωματισμός του χάρτη των ΗΠΑ με τέσσερα χρώματα (αγνοώντας τις λίμνες).

Ένα από τα πιο διάσημα προβλήματα την θεωρία γράφων είναι το θεώρημα των τεσσάρων χρωμάτων, δηλαδή ότι κάθε επίπεδος χάρτης μπορεί να χρωματιστεί με το πολύ τέσσερα χρώματα, έτσι ώστε όλες οι γειτονικές περιοχές να έχουν διαφορετικό χρώμα. Η εικασία φαίνεται να διατυπώθηκε για πρώτη φορά από τον Francis Guthrie.[12][13]

Πολλές λανθασμένες αποδείξεις έχουν προταθεί, συμπεριλαμβανομένων αυτές των Κέιλι, Kempe, και άλλων. Η μελέτη και η γενίκευση αυτού του προβλήματος από τους Tait, Heawood, Ramsey και Hadwiger οδήγησαν στην μελέτη των χρωματισμών γράφων σε επιφάνειες οποιουδήποτε γένους. Η αναδιατύπωση του Tait δημιούργησε μία νέα κλάση προβλημάτων, τα προβλήματα παραγοντοποίησης, ειδικά αυτών που μελετήθηκαν από τον Petersen και τον Kőnig. Οι εργασίες του Ramsey στους χρωματισμούς και πιο συγκεκριμένα στα αποτελέσματα που βρήκε ο Turán το 1941 οδήγησαν στην δημιουργία ενός άλλου κλάδου της θεωρίας γράφων, της ακραίας θεωρίας γράφων.

Το πρόβλημα των τεσσάρων χρωμάτων έμεινε ανοιχτό για πάνω από έναν αιώνα. Το 1969, ο Heinrich Heesch δημοσίευσε μία μέθοδο για την επίλυση του προβλήματος με την χρήση υπολογιστών.[14] Η απόδειξη με τη βοήθεια υπολογιστή από τους Kenneth Appel και Wolfgang Haken το 1976 κάνει σημαντική χρήση της έννοιας του "discharging" που αναπτύχθηκε από τον Heesch.[15][16] Για την απόδειξη χρειάστηκε να ελεγχθούν οι ιδιότητες 1,936 καταστάσεων με την χρήση υπολογιστή, και κάποιοι μαθηματικοί δεν την δέχτηκαν πλήρως λόγο της πολυπλοκότητάς της. Μία πιο απλή απόδειξη που ελέγχει μόνο 633 καταστάσεις παρουσιάστηκε από τους Robertson, Seymour, Sanders and Thomas.[17]

Η ανεξάρτητη ανάπτυξη της τοπολογίας από το 1860 έως το 1930 συνδυάστηκε με την θεωρία γράφων μέσα από τα έργα των Jordan, Kuratowski και Whitney. Άλλος ένας σημαντικός παράγοντας για την κοινή ανάπτυξη της θεωρίας γράφων και της τοπολογίας ήταν λόγω της χρήσης τεχνικών της μοντέρνας άλγεβρας. Το πρώτο παράδειγμα τέτοιας χρήστης ήταν στο έργο του φυσικού Γκούσταβ Κίρχοφ, ο οποίος το 1845 δημοσίευσε τους κανόνες του Κίρχοφ για τον υπολογισμό της διαφοράς δυναμικού και του ηλεκτρικού ρεύματος σε ένα ηλεκτρικό κύκλωμα.

Η εισαγωγή πιθανοτικών μεθόδων στην θεωρία γράφων, ειδικά μέσω της δουλειάς των Πολ Έρντος και Rényi για την ασυμπτωτική πιθανότητα της συνδεσιμότητας γράφων, οδήγησε σε άλλον έναν κλάδο, την θεωρία τυχαίων γράφων.

Περαιτέρω ανάγνωση[Επεξεργασία | επεξεργασία κώδικα]

Online κείμενα[Επεξεργασία | επεξεργασία κώδικα]

Σημειώσεις[Επεξεργασία | επεξεργασία κώδικα]

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]

  • Biggs, Norman· Lloyd, Edward Keith· Wilson, Robin J.· Wilson, Robin James (1986). Graph theory: 1736 - 1936 (1η έκδοση). Oxford: Clarendon Press. ISBN 978-0-19-853916-2. 
  • Cauchy, A.L. (1813). «Recherche sur les polyèdres - premier mémoire». Journal de l'Ecole Polytechnique 16 (9): 66–86. 
  • Cayley, A. (1875). «Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen». Berichte der deutschen Chemischen Gesellschaft (8): 1056–1059. 
  • L'Huillier, S.-A.-J. (1861). «Mémoire sur la polyèdrométrie». Annales de Mathématiques (3): 169–189. 
  • Μαυρονικόλας, Μάριος (2002). Διακριτά Μαθηματικά και Μαθηματική Λογική: Θεωρία Γράφων. Πάτρα: Ε.Α.Π. ISBN 960-538-461-2. 
  • Λευτέρης Κυρούσης· Χρήστος Μπούρας· Παύλος Σπυράκης· Γιάννης Σταματίου (2004). Εισαγωγή στους Γράφους Θεωρία, προβλήματα και λύσεις (2η έκδοση). Gutenberg. ISBN 978-960-01-0815-6. 

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

Ελληνικά άρθρα[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. 1,0 1,1 1,2 Μαυρονικόλας, Μάριος (2002). Διακριτά Μαθηματικά και Μαθηματική Λογική: Θεωρία Γράφων. Πάτρα: Ε.Α.Π. ISBN 960-538-461-2. 
  2. Δ. Σπινέλλης «Γράφοι», Οικονομικό Πανεπιστήμιο Αθηνών Αρχειοθετήθηκε 2010-01-02 στο Wayback Machine..
  3. Biggs, N.; Lloyd, E.; Wilson, R. (1986), Graph Theory, 1736-1936, Oxford University Press 
  4. Cauchy, A.L. (1813). «Recherche sur les polyèdres - premier mémoire». Journal de l'Ecole Polytechnique 9 (Cahier 16): 66–86. 
  5. L'Huillier, S.-A.-J. (1861). «Mémoire sur la polyèdrométrie». Annales de Mathématiques 3: 169–189. 
  6. Cayley, A. (1857), «On the theory of the analytical forms called trees», Philosophical Magazine, Series IV 13 (85): 172–176, doi:10.1017/CBO9780511703690.046, ISBN 9780511703690, https://rcin.org.pl/dlibra/docmetadata?showContent=true&id=173708 
  7. Cayley, A. (1875). «Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen». Berichte der deutschen Chemischen Gesellschaft 8: 1056–1059. doi:10.1002/cber.18750080252. .
  8. Sylvester, James Joseph (1878). «Chemistry and Algebra». Nature 17 (432): 284. doi:10.1038/017284a0. Bibcode1878Natur..17..284S. https://archive.org/stream/nature15unkngoog#page/n312/mode/1up. 
  9. Tutte, W.T. (2001), Graph Theory, Cambridge University Press, σελ. 30, ISBN 978-0-521-79489-3, https://books.google.com/books?id=uTGhooU37h4C&pg=PA30, ανακτήθηκε στις 2016-03-14 
  10. Gardner, Martin (1992), Fractal Music, Hypercards, and more…Mathematical Recreations from Scientific American, W. H. Freeman and Company, σελ. 203 
  11. Society for Industrial and Applied Mathematics (2002), «The George Polya Prize», Looking Back, Looking Ahead: A SIAM History, σελ. 26, http://www.siam.org/about/more/siam50.pdf, ανακτήθηκε στις 2016-03-14 
  12. May, Kenneth O. (1965). «The Origin of the Four-Color Conjecture». Isis 56 (3): 346-348. https://www.jstor.org/stable/228109. 
  13. O'Connor, J. J .· Robertson, E. F. «The four colour theorem». MacTutor. 
  14. Heinrich Heesch (1969). Untersuchungen zum Vierfarbenproblem. Mannheim: Bibliographisches Institut. 
  15. Appel, K.; Haken, W. (1977). «Every planar map is four colorable. Part I. Discharging». Illinois J. Math. 21 (3): 429–490. doi:10.1215/ijm/1256049011. https://archive.org/details/sim_illinois-journal-of-mathematics_1977-09_21_3/page/429. 
  16. Appel, K.; Haken, W. (1977). «Every planar map is four colorable. Part II. Reducibility». Illinois J. Math. 21 (3): 491–567. doi:10.1215/ijm/1256049012. https://archive.org/details/sim_illinois-journal-of-mathematics_1977-09_21_3/page/491. 
  17. Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R. (1997), «The four color theorem», Journal of Combinatorial Theory, Series B 70: 2–44, doi:10.1006/jctb.1997.1750