Το Θεώρημα των τεσσάρων χρωμάτων | PellaNews

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

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

Στις 23 Οκτώβριου  του 1852, ο Φράνσις Γκάθρι (Francis Guthrie) , προπτυχιακός φοιτητής  στο University College του Λονδίνου όταν προσπάθησε να χρωματίσει τον χάρτη των περιφερειών της Αγγλίας  αναρωτήθηκε ποιος θα ήταν ο ελάχιστος αριθμός διαφορετικών χρωμάτων τα οποία θα χρησιμοποιούσε ώστε οι γειτονικές περιφέρειες να έχουν διαφορετικό χρώμα. Δεν κατέληξε πουθενά  όποτε  έθεσε στον καθηγητή Αύγουστο  Ντε Μόργκαν (Augustus De Morgan) το ερώτημα. Ο Ντε Μόργκαν ήταν ο πρώτος καθηγητής μαθηματικών του νεοσύστατου πανεπιστήμιου University College και διάσημος για τις έρευνες του πάνω στην Λογική.

Όμως παρά την εξαιρετική του ευφυΐα, ο Ντε Μοργκαν δεν ήξερε την απάντηση στην ερώτηση του μαθητή του. Την ίδια μέρα έγραψε στον συνάδελφο του Χαμιλτον,  «τον εξυπνότερο άνθρωπο της Ιρλανδίας», στο Δουβλίνο.Ούτε  όμως ο Χάμιλτον γνώριζε την απάντηση και μέσα σε τρεις μέρες του έγραψε: «Δεν νομίζω να ασχοληθώ σύντομα με την τετράδα των χρωμάτων σου.»

Πολλοί μαθηματικοί μεγάλου βεληνεκούς δοκίμασαν την τύχη τους με το πρόβλημα, μάταια όμως. Χαρακτηριστικό παράδειγμα ο καλύτερος φίλος του Χιλμπερτ στο Γκετιγκεν, ο Χέρμαν Μινκοφσκι . Όταν το ερώτημα τέθηκε σε κάποιο από τα μαθήματα του, σχολίασε:
«Το θεώρημα δεν έχει ακόμα αποδειχτεί, αλλά αυτό οφείλεται στο ότι ασχολήθηκαν μαζί του μόνο μαθηματικοί τρίτης κατηγορίας». «Πιστεύω ότι μπορώ να το αποδείξω!!» Αφιέρωσε  αρκετά μαθήματα, παλεύοντας με διαφορές ιδέες  στον πίνακα. Τέλος, κάποιο πρωί, μπαίνοντας στην τάξη, έσκασε η βόμβα: «Οι ουρανοί εξοργίστηκαν από την αλαζονεία μου», ομολόγησε: «Η απόδειξη μου είναι ελαττωματική!»

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

Ο προφανής κανόνας είναι  ότι δυο γειτονικές χώρες  δεν πρέπει να έχουν το ίδιο χρώμα. Η ερώτηση του φρανσις Γκαθρι ήταν:
« μπορείτε να αποδείξετε ότι δεν χρειάζεστε πάνω από τέσσερα χρώματα για οποιονδήποτε χάρτη; »

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

Αν και οι μαθηματικοί δεν έδιναν δεκάρα για το αν η επίλυση του προβλήματος θα βοηθούσε τους χαρτογράφους η όχι, το η πρόκληση του ερωτήματος τους συνεπήρε. Για χρόνια ο Ντε Μοργκαν συνέχισε να ρωτά τους συναδέλφους του αν μπορούσαν αν βρουν μια απόδειξη μέχρι που τελικά ο Κεμπ ( Alfred Kempe ) ένας μαθηματικός  δημοσίευσε μια απόδειξη. Ο Κεμπ έγινε αρκετά διάσημος  ώστε τον δέχτηκαν στην Βασιλική εταιρεία και τον έχρισαν ιππότη. Βρέθηκε λοιπόν σε αρκετά αμήχανη θέση όταν η απόδειξη του αποδείχθηκε λανθασμένη από έναν άλλο μαθηματικό .Ο Χειγουντ (Percy Heawood), εργάστηκε για αρκετά χρόνια  πάνω στο ίδιο πρόβλημα και κατάφερε να αποδείξει ότι η απόδειξη του Κεμπ ήταν λανθασμένη.

Απόδειξη μέσω υπολογιστή

Ωστόσο πάλι οι μαθηματικοί δεν ήταν ικανοποιημένοι απόλυτα. Τα 5 χρώματα  πράγματι θα χρωμάτιζαν οποιοδήποτε χάρτη, αλλά τι γινόταν με τέσσερα η ακόμη και τρία;Η απόδειξη χρειάστηκε άλλα 80 χρόνια και ένα υπερυπολογιστή. Η πρώτη απόδειξη ήρθε το 1976 από τους Αμερικανούς μαθηματικούς Kenneth Appel και Wolfgang Haken από το Πανεπιστήμιο του  Illinois.

Οι μαθηματικοί αμφισβήτησαν την απόδειξη γιατί πραγματοποιήθηκε με την χρήση υπολογιστή, κανείς δεν μπορεί να επιβεβαιώσει ότι στον κώδικα του υπολογιστή δεν παραβλέφτηκε κάποια περίπτωση. Είναι πλέον διάσημο το αστείο που έκανε ο Μάρτιν Γκάρντνερ στην στήλη του με τις σπαζοκεφαλιές  στο scientific American το 1975. Μόλις ένα χρόνο μετά την απόδειξη, πρότεινε ένα χάρτη 110 περιφερειών στον οποίο όπως υποστήριζε απαιτούνταν  5  χρώματα. Χρησιμοποιήθηκε όμως το πρόγραμμα mathematica  και έγινε ο χρωματισμός με 4 χρώματα. Δείτε το παρακάτω σχήμα:

Το 2004 οι Georges Gonthier των εργαστηρίων της Microsoft στη Βρετανία και Benjamin Werner στο INRIA της Γαλλίας υποστηρίζουν ότι επιβεβαίωσαν  την απόδειξη. Οι ερευνητές μετέγραψαν την απόδειξη στη γλώσσα υπολογιστή Coq, η οποία χρησιμοποιείται για την αναπαράσταση λογικών προτάσεων και ανέπτυξαν ένα λογισμικό ελέγχου λογικής προκειμένου να επιβεβαιώσουν ότι κάθε βήμα που οδηγεί στην απόδειξη είναι σωστό.

Από τη Μαθηματικό, Ελένη Μαυρίδου!

Τηλέφωνο επικοινωνίας : 6932525750

Emailεπικοινωνίας :eukleidis24@gmail.com