Θεώρημα των τεσσάρων χρωμάτων

Στα μαθηματικά το θεώρημα των τεσσάρων χρωμάτων, ή το θεώρημα των χαρτών των τεσσάρων χρωμάτων δηλώνει ότι, δεδομένου του διαχωρισμού ενός επιπέδου σε γειτονικές περιοχές, παράγοντας έτσι ένα χάρτη, δεν απαιτούνται περισσότερα από τέσσερα χρώματα για να χρωματιστούν οι περιοχές του χάρτη, έτσι ώστε να μην υπάρχουν δύο γειτονικές περιοχές με τα ίδια χρώματα. Δύο περιοχές ονομάζονται γειτονικές αν έχουν ένα κοινό σύνορο, χωρίς να σχηματίζουν κορυφή, καθώς οι κορυφές αποτελούν σημεία που είναι κοινά για τρεις ή περισσότερες περιοχές.Για παράδειγμα, στο χάρτη των Ηνωμένων Πολιτειών της Αμερικής, η Γιούτα και η Αριζόνα είναι γειτονικές πολιτείες, αλλά η Γιούτα και το Νέο Μεξικό, οι οποίες έχουν μόνο ένα κοινό σημείο το οποίο ανήκει επίσης στην Αριζόνα και το Κολοράντο, δεν είναι.
Παρά το κίνητρο του χρωματισμού των πολιτικών χαρτών των χωρών, το θεώρημα δεν έχει βρει την ανάλογη ανταπόκριση από τους σχεδιαστές των χαρτών. Σύμφωνα με ένα άρθρο του ιστορικού μαθηματικού Κένεθ Μέι (Kenneth May) (Wilson 2002, 2), «οι χάρτες που χρησιμοποιούν μόνο τέσσερα χρώματα είναι σπάνιοι, αλλά και εκείνοι που χρησιμοποιούν συνήθως απαιτούν μόνο τρία. Τα βιβλία για τη χαρτογραφία και η ιστορία της σχεδίασης χαρτών δεν αναφέρουν την ιδιότητα των τεσσάρων χρωμάτων».
Τρία χρώματα αρκούν για τους πιο απλούς χάρτες, αλλά ένα επιπλέον τέταρτο χρώμα είναι απαραίτητο για κάποιους χάρτες, όπως ένας χάρτης στον οποίο μία περιοχή περιβάλλεται από έναν περιττό αριθμό άλλων περιοχών που συνορεύουν σε έναν κύκλο. Το θεώρημα των πέντε χρωμάτων, το οποίο έχει μια μικρή απόδειξη σε αρχικό στάδιο, δηλώνει ότι πέντε χρώματα αρκούν για να χρωματίσουν έναν χάρτη, και είχε αποδειχθεί στα τέλη του 19ου αιώνα (Heawood 1890)∙ ωστόσο, η απόδειξη του αξιώματος ότι τέσσερα χρώματα αρκούν, αποδείχθηκε να είναι ιδιαίτερα δυσκολότερη. Μετά την πρώτη δήλωση του θεωρήματος των τεσσάρων χρωμάτων, το 1852, εμφανίστηκαν πολλές αναληθείς αποδείξεις και αναληθή αντιπαραδείγματα.
Το θεώρημα των τεσσάρων χρωμάτων αποδείχθηκε το 1976 από τον Kenneth Appel και τον Wolfgang Haken. Ήταν το πρώτο σημαντικό θεώρημα που αποδείχθηκε με τη χρήση ηλεκτρονικού υπολογιστή. Η προσέγγιση του Appel και του Haken ξεκίνησε αποδεικνύοντας ότι υπάρχει ένας συγκεκριμένος αριθμός 1.936 χαρτών, ο καθένας από τους οποίους δεν μπορεί να αποτελέσει μέρος ενός από τα μικρότερου μεγέθους αντιπαραδείγματα του θεωρήματος των τεσσάρων χρωμάτων. Οι Appel και Haken χρησιμοποίησαν ένα ειδικά φτιαγμένο πρόγραμμα υπολογιστή για να επιβεβαιώσει ότι καθένας από αυτούς τους χάρτες είχε αυτήν την ιδιότητα. Επιπλέον, οποιοσδήποτε χάρτης (ανεξάρτητα από το αν είναι αντιπαράδειγμα ή όχι) θα πρέπει να έχει μία περιοχή που να μοιάζει με έναν από εκείνους τους 1.936 χάρτες. Για να αποδειχθεί αυτό απαιτήθηκαν εκατοντάδες σελίδες χειρόγραφων αναλύσεων. Ο Appel και ο Haken συμπέραναν ότι δεν υπήρχαν μικρότερα αντιπαραδείγματα, καθώς κάποιος θα πρέπει να περιλαμβάνει, αν και δεν περιλαμβάνει, έναν από αυτούς τους 1.936 χάρτες. Αυτή η αντίφαση δείχνει ότι δεν υπάρχουν καθόλου αντιπαραδείγματα και ότι, κατά συνέπεια, το θεώρημα είναι αληθές. Αρχικά, η απόδειξή τους δεν έγινε αποδεκτή από όλους τους μαθηματικούς, καθώς οι υποβοηθούμενες από υπολογιστή αποδείξεις δεν ήταν εφικτό να ελεγχθούν από τον άνθρωπο (Swart 1980). Από τότε η απόδειξη του θεωρήματος έχει κερδίσει ευρύτερη αποδοχή, παρόλο που οι αμφιβολίες παραμένουν (Wilson 2002, 216-222).
Για να διαλυθούν οι αμφιβολίες που παρέμεναν σχετικά με την απόδειξη των Appel – Haken, το 1997 δημοσιεύθηκε μία απλούστερη απόδειξη, που χρησιμοποιούσε την ίδια ιδέα και παρέμενε βασισμένη σε υπολογιστές, από τους Robertson, Sanders, Seymour, και Thomas. Επιπλέον, το 2005, το θεώρημα αποδείχθηκε από τον Georges Gonthier με λογισμικό απόδειξης γενικών θεωρημάτων.

Ακριβής διατύπωση του θεωρήματος

Ο διαισθητική δήλωση του θεωρήματος των τεσσάρων χρωμάτων, δηλαδή ότι, «αν δοθεί οποιοσδήποτε διαχωρισμός ενός επιπέδου σε γειτονικές περιοχές, που καλείται χάρτης, οι περιοχές είναι δυνατό να χρωματιστούν χρησιμοποιώντας το πολύ τέσσερα χρώματα, έτσι ώστε δύο γειτονικές περιοχές να μην έχουν το ίδιο χρώμα», θα πρέπει να ερμηνευθεί κατάλληλα για να είναι ορθός. Πρώτον, όλες οι κορυφές, σημεία που ανήκουν (τεχνικά, είναι στα όρια) σε τρεις ή περισσότερες χώρες, θα πρέπει να αγνοηθούν. Επιπλέον, οι αλλόκοτοι χάρτες (χάρτες που χρησιμοποιούν περιοχές πεπερασμένης έκτασης αλλά απεριόριστης περιμέτρου) μπορεί να απαιτούν περισσότερα από τέσσερα χρώματα. 
Δεύτερον, για τους σκοπούς του θεωρήματος, κάθε «χώρα» θα πρέπει να είναι μία περιοχή που απλά ενώνεται με μία άλλη ή είναι γειτονική. Στον πραγματικό κόσμο, αυτό δεν είναι αληθές (π.χ., η Αλάσκα ως μέρος των Ηνωμένων Πολιτειών, το Ναχιτσεβάν ως μέρος του Αζερμπαϊτζάν και το Καλίνινγκραντ ως μέρος της Ρωσίας δεν είναι γειτονικές περιοχές). Εξαιτίας του ότι το έδαφος  μίας συγκεκριμένης χώρας πρέπει να είναι του ίδιου χρώματος, τα τέσσερα χρώματα μπορεί να μην είναι αρκετά. Για παράδειγμα, σκεφτείτε τον παρακάτω απλοποιημένο χάρτη:
Σε αυτόν το χάρτη, οι δύο περιοχές με την ετικέτα Α ανήκουν στην ίδια χώρα και πρέπει να είναι του ιδίου χρώματος. Αυτός ο χάρτης απαιτεί πέντε χρώματα, δεδομένου ότι οι δύο περιοχές Α μαζί είναι γειτονικές με τέσσερις άλλες περιοχές, καθεμία από τις οποίες είναι γειτονική με όλες τις υπόλοιπες. Αν η περιοχή Α αποτελούταν από τρεις περιοχές, μπορεί να χρειάζονταν έξι ή περισσότερα χρώματα ∙ κάποιος μπορεί κάλλιστα να σχεδιάσει χάρτες που να απαιτούν έναν αυθαίρετα μεγάλο αριθμό χρωμάτων. Ένας παρόμοιος σχεδιασμός ενός χάρτη μπορεί επίσης να ισχύσει αν χρησιμοποιηθεί ένα μόνο χρώμα για όλα τα σημεία με νερό, όπως συμβαίνει συνήθως και στους πραγματικούς χάρτες. 
Μία ευκολότερη εκδοχή του θεωρήματος χρησιμοποιεί θεωρία γραφημάτων. Το σύνολο των περιοχών ενός χάρτη μπορεί να απεικονιστεί πιο αφηρημένα ως ένα γράφημα με απόκλιση, το οποίο έχει μία κορυφή για την κάθε περιοχή και μία άκρη για κάθε ζεύγος περιοχών που έχουν ένα κοινό σύνορο. Το γράφημα είναι επίπεδο (μιλάμε για τα γραφήματα που έχουν κάποιους περιορισμούς αναφορικά μόνο με το χάρτη από τον οποίο έχουν τροποποιηθεί): μπορεί να σχεδιαστεί στο επίπεδο χωρίς κοινά σημεία, τοποθετώντας κάθε κορυφή σε μία αυθαίρετα επιλεγμένη τοποθεσία μέσα στην περιοχή με την οποία συνορεύει και σχεδιάζοντας τις κορυφές ως καμπύλες που οδηγούν, χωρίς να υπάρχουν κοινά σημεία μεταξύ των περιοχών, από την τοποθεσία της κορυφής σε κάθε κοινό συνοριακό σημείο των περιοχών. Αντιστρόφως, από ένα χάρτη μπορεί να σχεδιαστεί οποιοδήποτε επίπεδο γράφημα με αυτόν τον τρόπο. Σύμφωνα με την ορολογία της θεωρίας των γραφημάτων, το θεώρημα των τεσσάρων χρωμάτων δηλώνει ότι οι κορυφές οποιουδήποτε επίπεδου γραφήματος μπορούν να χρωματιστούν με τέσσερα χρώματα κατ’ ανώτατο όριο, έτσι ώστε να μην υπάρχουν δύο γειτονικές κορυφές του ιδίου χρώματος, ή με λίγα λόγια, «κάθε επίπεδο γράφημα μπορεί να χρωματιστεί με τέσσερα χρώματα» (Thomas 1998, σελ. 849∙ Wilson 2002).

Πρώιμες προσπάθειες απόδειξης

Η εικασία προτάθηκε πρώτη φορά στις 23 Οκτωβρίου του 1852 όταν ο Francis Guthrie, ενώ προσπαθούσε να χρωματίσει το χάρτη των χωρών της Αγγλίας, παρατήρησε ότι χρειάζονταν μόνο τέσσερα διαφορετικά χρώματα. Εκείνη την εποχή, ο αδερφός του Guthrie, ο Frederick, ήταν μαθητής του Augustus De Morgan στο University College. Ο Francis ερευνούσε υπό την επίβλεψη του Frederick, ο οποίος μετέφερε την εικασία στον De Morgan (ο Francis Guthrie αποφοίτησε αργότερα το 1852, και έπειτα έγινε καθηγητής μαθηματικών στη Νότια Αφρική). Σύμφωνα με τον De Morgan:
“Ένας μαθητής μου [Guthrie] μου ζήτησε σήμερα να του δώσω μία αιτιολογία για ένα γεγονός, το οποίο δε γνώριζα ότι είναι γεγονός – και ακόμα δεν το γνωρίζω. Ισχυρίζεται ότι αν ένα σώμα διαχωριστεί με οποιονδήποτε τρόπο και τα μέρη του χρωματιστούν διαφορετικά, έτσι ώστε τα σώματα με οποιοδήποτε κομμάτι κοινής διαχωριστικής γραμμής να χρωματίζονται διαφορετικά – μπορεί να χρειάζονται τέσσερα χρώματα αλλά όχι περισσότερα – το ακόλουθο είναι η δική του εκδοχή κατά την οποία τέσσερα χρώματα απαιτούνται. Το ερώτημα για το αν χρειάζονται πέντε ή περισσότερα χρώματα μένει να απαντηθεί…» (Wilson 2002, σελ. 18).
Ο “F.G.”, ίσως ένας από τους δύο Guthrie, δημοσίευσε το ερώτημα στο The Athenaeum το 1854, και ο De Morgan έθεσε το ερώτημα και πάλι στο ίδιο το περιοδικό το 1860. Μία ακόμα αναφορά που δημοσιεύθηκε εκείνο το πρώιμο διάστημα ήταν από τον Arthur Cayley (1879), η οποία αναγνωρίζει την εικασία του De Morgan.
 
Δεν ήταν λίγες οι πρώιμες, αποτυχημένες προσπάθειες για την απόδειξη του θεωρήματος. Μία απόδειξη δόθηκε από τον Alfred Kempe το 1879, η οποία αναγνωρίστηκε ευρέως ∙ μία άλλη δόθηκε από τον Peter Guthrie Tait το 1880. Η απόδειξη του Kempe θεωρούνταν σωστή μέχρι το 1890, όταν αποδείχθηκε αναληθής από τον Percy Heawood, και το 1891 η απόδειξη του Tait αποδείχθηκε επίσης αναληθής από τον Julius Petersen – καθεμία από τις αναληθείς αποδείξεις παρέμενε αδιαμφισβήτητη για 11 χρόνια(Thomas 1998, σελ. 848). 
To 1890, επιπρόσθετα με την έκθεση του σφάλματος στην απόδειξη του Kempe, ο Heawood απέδειξε το θεώρημα των πέντε χρωμάτων (Heawood 1890) και γενίκευσε την εικασία των τεσσάρων χρωμάτων σε επιφάνειες αυθαίρετου γένους – δείτε παρακάτω. 
Το 1880, ο Tait απέδειξε ότι το θεώρημα των τεσσάρων χρωμάτων είναι ισοδύναμο με τη δήλωση ότι ένας συγκεκριμένος τύπος γραφήματος (ο οποίος καλείται snark στην μοντέρνα ορολογία) πρέπει να είναι μη επίπεδος.
Το 1943, ο Hugo Hadwiger διατύπωσε την εικασία του Hadwiger  (Hadwiger 1943), μία εκτεταμένη γενίκευση του προβλήματος των τεσσάρων χρωμάτων, η οποία παραμένει άλυτη μέχρι και σήμερα.

Απλοποίηση και επαλήθευση

Από τη στιγμή που αποδείχθηκε το θεώρημα, αποτελεσματικοί αλγόριθμοι έχουν βρεθεί για χάρτες 4 χρωμάτων, που απαιτούν μόνο O (n²) χρόνο – ταξινόμηση φυσαλίδας που απαιτεί χρόνο (n²)- όπου n είναι ο αριθμός των κορυφών. Το 1996, οι Neil Robertson, Daniel P.Sanders, Paul Seymour και Robin Thomas δημιούργησαν έναν αλγόριθμο τετραγωνικού χρόνου (quadratic time algorithm), βελτιώνοντας έναν τετάρτου χρόνου αλγόριθμο (quartic algorithm) που ήταν βασισμένος στην απόδειξη των Appel και Haken (Thomas 1995; Robertson και άλλοι 1996). Αυτή η καινούργια απόδειξη είναι παρόμοια με αυτή των Appel και Haken, αλλά πιο αποτελεσματική, γιατί μείωσε την πολυπλοκότητα του προβλήματος και απαιτούσε τον έλεγχο μόνο 633 μειώσιμων διαμορφώσεων. Το αναπόφευκτο και το μειώσιμο κομμάτι αυτής της νέας απόδειξης πρέπει να εκτελεστεί από τον υπολογιστή και είναι πρακτικά αδύνατο να ελεγθεί με το χέρι (Thomas 1998, σελίδες 852–853). Το 2001, οι ίδιοι συγγραφείς ανακοίνωσαν μια εναλλακτική λύση, αποδεικνύοντας το θεώρημα snark (snark theorem-Thomas; Pegg και άλλοι 2002).
Το 2005 οι Benjamin Werner και Georges Gonthier, επισημοποίησαν μια απόδειξη του θεωρήματος μέσα στο βοηθό αποδείξεων Coq. Αυτό απομάκρυνε την ανάγκη να εμπιστευτούμε τα διάφορα προγράμματα υπολογιστή που χρησιμοποιούνται για να επιβεβαιώσουν συγκεκριμένες υποθέσεις·  απαιτείται μόνο να εμπιστευτούμε τον πυρήνα Coq (Gonthier 2008).