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

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

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

Για τους σκοπούς του θεωρήματος, κάθε "χώρα" πρέπει να είναι μια απλά συνδεδεμένη περιοχή, ή συνεχής. Στον πραγματικό κόσμο, αυτό δεν ισχύει: Η Αλάσκα ως τμήμα των Ηνωμένων Πολιτειών, το Ναχτσιβάν ως τμήμα του Αζερμπαϊτζάν και το Καλίνινγκραντ ως τμήμα της Ρωσίας δεν είναι συνεχόμενες. Επειδή το έδαφος μιας συγκεκριμένης χώρας πρέπει να έχει το ίδιο χρώμα, τέσσερα χρώματα μπορεί να μην είναι αρκετά. Για παράδειγμα, θεωρήστε έναν απλουστευμένο χάρτη, όπως αυτός που φαίνεται στα αριστερά: Σε αυτόν τον χάρτη, οι δύο περιοχές με την ένδειξη Α ανήκουν στην ίδια χώρα και πρέπει να έχουν το ίδιο χρώμα. Αυτός ο χάρτης απαιτεί τότε πέντε χρώματα, αφού οι δύο περιοχές Α μαζί συνορεύουν με τέσσερις άλλες περιοχές, καθεμία από τις οποίες συνορεύει με όλες τις άλλες. Αν η Α είχε μόνο τρεις περιοχές, θα χρειάζονταν έξι ή περισσότερα χρώματα. Με αυτόν τον τρόπο, είναι δυνατόν να φτιάξετε χάρτες που χρειάζονται αυθαίρετα μεγάλο αριθμό χρωμάτων. Μια παρόμοια κατασκευή ισχύει επίσης εάν χρησιμοποιείται ένα μόνο χρώμα για όλα τα υδάτινα σώματα, όπως συνηθίζεται στους πραγματικούς χάρτες.

Μια πιο εύκολη στη διατύπωση εκδοχή του θεωρήματος χρησιμοποιεί τη θεωρία γραφημάτων. Το σύνολο των περιοχών ενός χάρτη μπορεί να αναπαρασταθεί πιο αφηρημένα ως ένα μη κατευθυνόμενο γράφημα που έχει μια κορυφή για κάθε περιοχή και μια ακμή για κάθε ζεύγος περιοχών που μοιράζονται ένα οριακό τμήμα. Το γράφημα αυτό είναι επίπεδο: μπορεί να σχεδιαστεί στο επίπεδο χωρίς διασταυρώσεις τοποθετώντας κάθε κορυφή σε μια αυθαίρετα επιλεγμένη θέση εντός της περιοχής στην οποία αντιστοιχεί και σχεδιάζοντας τις ακμές ως καμπύλες που οδηγούν χωρίς διασταύρωση εντός κάθε περιοχής από τη θέση της κορυφής σε κάθε κοινό οριακό σημείο της περιοχής. Αντίστροφα, κάθε επίπεδο γράφημα μπορεί να σχηματιστεί από ένα χάρτη με αυτόν τον τρόπο. Στη γραφοθεωρητική ορολογία, το θεώρημα των τεσσάρων χρωμάτων δηλώνει ότι οι κορυφές κάθε επίπεδου γραφήματος μπορούν να χρωματιστούν με το πολύ τέσσερα χρώματα, έτσι ώστε καμία από τις δύο γειτονικές κορυφές να μην έχει το ίδιο χρώμα, ή για συντομία, "κάθε επίπεδο γράφημα είναι τετράχρωμο" (Thomas 1998, σ. 849- Wilson 2002).

Παράδειγμα χάρτη του Αζερμπαϊτζάν με μη συνεχόμενες περιοχές


Αυτός ο χάρτης δεν μπορεί να χρωματιστεί με τέσσερα χρώματα

Ιστορία

Ο πρώτος που ονόμασε το πρόβλημα ήταν ο Francis Guthrie, το 1852. Ήταν φοιτητής νομικής στην Αγγλία εκείνη την εποχή. Διαπίστωσε ότι χρειαζόταν τουλάχιστον τέσσερα χρώματα για να χρωματίσει έναν χάρτη με τις κομητείες της Αγγλίας. Ο Augustus de Morgan συζήτησε για πρώτη φορά το πρόβλημα, σε μια επιστολή που έγραψε στον Rowan Hamliton τον Αύγουστο του 1852. Στην επιστολή, ο ντε Μόργκαν ρωτάει αν τέσσερα χρώματα είναι πραγματικά αρκετά για να χρωματίσει έναν χάρτη, έτσι ώστε οι χώρες που βρίσκονται η μία δίπλα στην άλλη να παίρνουν διαφορετικά χρώματα.

Ο Άγγλος μαθηματικός Arthur Cayley παρουσίασε το πρόβλημα στη μαθηματική εταιρεία του Λονδίνου το 1878. Μέσα σε ένα χρόνο, ο Alfred Kempe βρήκε κάτι που έμοιαζε με απόδειξη του προβλήματος. Έντεκα χρόνια αργότερα, το 1890, ο Percy Heawood έδειξε ότι η απόδειξη του Alfred ήταν λανθασμένη. Ο Peter Guthrie Tait παρουσίασε μια άλλη απόπειρα απόδειξης το 1880. Χρειάστηκαν έντεκα χρόνια για να αποδειχθεί ότι ούτε η απόδειξη του Tait λειτουργούσε. Το 1891, ο Julius Petersen μπόρεσε να το δείξει αυτό. Όταν διέψευσε την απόδειξη του Cayley, ο Kempe έδειξε επίσης μια απόδειξη για ένα πρόβλημα που ονόμασε θεώρημα πέντε χρωμάτων. Το θεώρημα λέει ότι οποιοσδήποτε τέτοιος χάρτης μπορεί να χρωματιστεί με όχι περισσότερα από πέντε χρώματα. Υπάρχουν δύο περιορισμοί: Πρώτον, κάθε χώρα είναι συνεχόμενη, δεν υπάρχουν αποκλεισμοί. Ο δεύτερος περιορισμός είναι ότι οι χώρες πρέπει να έχουν κοινά σύνορα- αν αγγίζουν μόνο σε ένα σημείο, μπορούν να χρωματιστούν με το ίδιο χρώμα. Παρόλο που η απόδειξη του Kempe ήταν λανθασμένη, χρησιμοποίησε μερικές από τις ιδέες που θα επέτρεπαν αργότερα μια σωστή απόδειξη.

Στις δεκαετίες του 1960 και 1970, ο Heinrich Heesch ανέπτυξε ένα πρώτο σχέδιο απόδειξης μέσω υπολογιστή. Ο Kenneth Appel και ο Wolfgang Haken βελτίωσαν αυτό το σκίτσο το 1976 (Robertson et al. 1996). Κατάφεραν να μειώσουν τον αριθμό των περιπτώσεων που θα έπρεπε να ελεγχθούν σε 1936- μια μεταγενέστερη έκδοση έγινε που στηριζόταν στη δοκιμή μόνο 1476 περιπτώσεων. Κάθε περίπτωση έπρεπε να δοκιμαστεί από έναν υπολογιστή (Appel & Haken 1977).

Το 1996, οι Neil Robertson, Daniel Sanders, Paul Seymour και Robin Thomas βελτίωσαν τη μέθοδο και μείωσαν τον αριθμό των περιπτώσεων που έπρεπε να εξεταστούν σε 663. Και πάλι, κάθε περίπτωση έπρεπε να ελεγχθεί με υπολογιστή.

Το 2005, οι Georges Gonthier και Benjamin Werner ανέπτυξαν μια επίσημη απόδειξη. Αυτό ήταν μια βελτίωση, επειδή επέτρεψε τη χρήση λογισμικού για την απόδειξη θεωρημάτων, για πρώτη φορά. Το λογισμικό που χρησιμοποιήθηκε ονομάζεται Coq.

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

Προσπάθειες που αποδείχθηκαν λανθασμένες

Το θεώρημα των τεσσάρων χρωμάτων είναι πασίγνωστο για το γεγονός ότι στη μακρά ιστορία του έχει προσελκύσει μεγάλο αριθμό ψευδών αποδείξεων και διαψεύσεων. Στην αρχή, οι New York Times αρνήθηκαν να αναφέρουν την απόδειξη Appel-Haken. Η εφημερίδα το έκανε αυτό για λόγους πολιτικής- φοβόταν ότι η απόδειξη θα αποδεικνυόταν ψευδής όπως και οι προηγούμενες (Wilson 2002, σ. 209). Ορισμένες αποδείξεις χρειάστηκαν πολύ χρόνο, μέχρι να μπορέσουν να διαψευστούν: Για τις αποδείξεις του Kempe και του Tait η παραποίησή τους χρειάστηκε πάνω από μια δεκαετία.

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

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

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

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

Χρωματισμός πολιτικών χαρτών

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

Επέκταση σε "μη επίπεδους" χάρτες

Το θεώρημα των τεσσάρων χρωμάτων απαιτεί ο "χάρτης" να βρίσκεται σε μια επίπεδη επιφάνεια, αυτό που οι μαθηματικοί αποκαλούν επίπεδο. Το 1890, ο Percy John Heawood δημιούργησε αυτό που σήμερα ονομάζεται εικασία Heawood: Θέτει το ίδιο ερώτημα με το θεώρημα των τεσσάρων χρωμάτων, αλλά για οποιοδήποτε τοπολογικό αντικείμενο. Για παράδειγμα, ένας τόρος μπορεί να χρωματιστεί με το πολύ επτά χρώματα. Η εικασία Heawood δίνει έναν τύπο που λειτουργεί για όλα αυτά τα αντικείμενα, εκτός από το μπουκάλι Klein.