Θεώρημα των τεσσάρων χρωμάτων
From Wikipedia, the free encyclopedia
Στα μαθηματικά το θεώρημα των τεσσάρων χρωμάτων, ή το θεώρημα των χαρτών των τεσσάρων χρωμάτων δηλώνει ότι, δεδομένου του διαχωρισμού ενός επιπέδου σε γειτονικές περιοχές, παράγοντας έτσι ένα χάρτη, δεν απαιτούνται περισσότερα από τέσσερα χρώματα για να χρωματιστούν οι περιοχές του χάρτη, έτσι ώστε να μην υπάρχουν δύο γειτονικές περιοχές με τα ίδια χρώματα. Δύο περιοχές ονομάζονται γειτονικές αν έχουν ένα κοινό σύνορο, χωρίς να σχηματίζουν κορυφή, καθώς οι κορυφές αποτελούν σημεία που είναι κοινά για τρεις ή περισσότερες περιοχές.[1] Για παράδειγμα, στο χάρτη των Ηνωμένων Πολιτειών της Αμερικής, η Γιούτα και η Αριζόνα είναι γειτονικές πολιτείες, αλλά η Γιούτα και το Νέο Μεξικό, οι οποίες έχουν μόνο ένα κοινό σημείο το οποίο ανήκει επίσης στην Αριζόνα και το Κολοράντο, δεν είναι.
Παρά το κίνητρο του χρωματισμού των πολιτικών χαρτών των χωρών, το θεώρημα δεν έχει βρει την ανάλογη ανταπόκριση από τους σχεδιαστές των χαρτών. Σύμφωνα με ένα άρθρο του ιστορικού μαθηματικού Κένεθ Μέι (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 με λογισμικό απόδειξης γενικών θεωρημάτων.