.
Στα μαθηματικά το θεώρημα των τεσσάρων χρωμάτων, ή το θεώρημα των χαρτών των τεσσάρων χρωμάτων δηλώνει ότι, δεδομένου του διαχωρισμού ενός επιπέδου σε γειτονικές περιοχές, παράγοντας έτσι ένα χάρτη, δεν απαιτούνται περισσότερα από τέσσερα χρώματα για να χρωματιστούν οι περιοχές του χάρτη, έτσι ώστε να μην υπάρχουν δύο γειτονικές περιοχές με τα ίδια χρώματα. Δύο περιοχές ονομάζονται γειτονικές αν έχουν ένα κοινό σύνορο, χωρίς να σχηματίζουν κορυφή, καθώς οι κορυφές αποτελούν σημεία που είναι κοινά για τρεις ή περισσότερες περιοχές.[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 με λογισμικό απόδειξης γενικών θεωρημάτων.
Ακριβής διατύπωση του θεωρήματος
Ο διαισθητική δήλωση του θεωρήματος των τεσσάρων χρωμάτων, δηλαδή ότι, «αν δοθεί οποιοσδήποτε διαχωρισμός ενός επιπέδου σε γειτονικές περιοχές, που καλείται χάρτης, οι περιοχές είναι δυνατό να χρωματιστούν χρησιμοποιώντας το πολύ τέσσερα χρώματα, έτσι ώστε δύο γειτονικές περιοχές να μην έχουν το ίδιο χρώμα», θα πρέπει να ερμηνευθεί κατάλληλα για να είναι ορθός. Πρώτον, όλες οι κορυφές, σημεία που ανήκουν (τεχνικά, είναι στα όρια) σε τρεις ή περισσότερες χώρες, θα πρέπει να αγνοηθούν. Επιπλέον, οι αλλόκοτοι χάρτες (χάρτες που χρησιμοποιούν περιοχές πεπερασμένης έκτασης αλλά απεριόριστης περιμέτρου) μπορεί να απαιτούν περισσότερα από τέσσερα χρώματα. [2]
Ο χάρτης του Αζερμπαϊτζάν είναι παράδειγμα χάρτη με ασυνεχείς περιοχές.
Δεύτερον, για τους σκοπούς του θεωρήματος, κάθε «χώρα» θα πρέπει να είναι μία περιοχή που απλά ενώνεται με μία άλλη ή είναι γειτονική. Στον πραγματικό κόσμο, αυτό δεν είναι αληθές (π.χ., η Αλάσκα ως μέρος των Ηνωμένων Πολιτειών, το Ναχιτσεβάν ως μέρος του Αζερμπαϊτζάν και το Καλίνινγκραντ ως μέρος της Ρωσίας δεν είναι γειτονικές περιοχές). Εξαιτίας του ότι το έδαφος μίας συγκεκριμένης χώρας πρέπει να είναι του ίδιου χρώματος, τα τέσσερα χρώματα μπορεί να μην είναι αρκετά. Για παράδειγμα, σκεφτείτε τον παρακάτω απλοποιημένο χάρτη:
Σε αυτόν το χάρτη, οι δύο περιοχές με την ετικέτα Α ανήκουν στην ίδια χώρα και πρέπει να είναι του ιδίου χρώματος. Αυτός ο χάρτης απαιτεί πέντε χρώματα, δεδομένου ότι οι δύο περιοχές Α μαζί είναι γειτονικές με τέσσερις άλλες περιοχές, καθεμία από τις οποίες είναι γειτονική με όλες τις υπόλοιπες. Αν η περιοχή Α αποτελούταν από τρεις περιοχές, μπορεί να χρειάζονταν έξι ή περισσότερα χρώματα ∙ κάποιος μπορεί κάλλιστα να σχεδιάσει χάρτες που να απαιτούν έναν αυθαίρετα μεγάλο αριθμό χρωμάτων. Ένας παρόμοιος σχεδιασμός ενός χάρτη μπορεί επίσης να ισχύσει αν χρησιμοποιηθεί ένα μόνο χρώμα για όλα τα σημεία με νερό, όπως συμβαίνει συνήθως και στους πραγματικούς χάρτες.
Μία ευκολότερη εκδοχή του θεωρήματος χρησιμοποιεί θεωρία γραφημάτων. Το σύνολο των περιοχών ενός χάρτη μπορεί να απεικονιστεί πιο αφηρημένα ως ένα γράφημα με απόκλιση, το οποίο έχει μία κορυφή για την κάθε περιοχή και μία άκρη για κάθε ζεύγος περιοχών που έχουν ένα κοινό σύνορο. Το γράφημα είναι επίπεδο (μιλάμε για τα γραφήματα που έχουν κάποιους περιορισμούς αναφορικά μόνο με το χάρτη από τον οποίο έχουν τροποποιηθεί): μπορεί να σχεδιαστεί στο επίπεδο χωρίς κοινά σημεία, τοποθετώντας κάθε κορυφή σε μία αυθαίρετα επιλεγμένη τοποθεσία μέσα στην περιοχή με την οποία συνορεύει και σχεδιάζοντας τις κορυφές ως καμπύλες που οδηγούν, χωρίς να υπάρχουν κοινά σημεία μεταξύ των περιοχών, από την τοποθεσία της κορυφής σε κάθε κοινό συνοριακό σημείο των περιοχών. Αντιστρόφως, από ένα χάρτη μπορεί να σχεδιαστεί οποιοδήποτε επίπεδο γράφημα με αυτόν τον τρόπο. Σύμφωνα με την ορολογία της θεωρίας των γραφημάτων, το θεώρημα των τεσσάρων χρωμάτων δηλώνει ότι οι κορυφές οποιουδήποτε επίπεδου γραφήματος μπορούν να χρωματιστούν με τέσσερα χρώματα κατ’ ανώτατο όριο, έτσι ώστε να μην υπάρχουν δύο γειτονικές κορυφές του ιδίου χρώματος, ή με λίγα λόγια, «κάθε επίπεδο γράφημα μπορεί να χρωματιστεί με τέσσερα χρώματα» (Thomas 1998, σελ. 849∙ Wilson 2002).
Ιστορικά στοιχεία
Πρώιμες προσπάθειες απόδειξης
Η εικασία προτάθηκε πρώτη φορά στις 23 Οκτωβρίου του 1852[3] όταν ο 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,[4] [5]και ο De Morgan έθεσε το ερώτημα και πάλι στο ίδιο το περιοδικό το 1860.[6] Μία ακόμα αναφορά που δημοσιεύθηκε εκείνο το πρώιμο διάστημα ήταν από τον 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 στην μοντέρνα ορολογία) πρέπει να είναι μη επίπεδος.[7]
Το 1943, ο Hugo Hadwiger διατύπωσε την εικασία του Hadwiger (Hadwiger 1943), μία εκτεταμένη γενίκευση του προβλήματος των τεσσάρων χρωμάτων, η οποία παραμένει άλυτη μέχρι και σήμερα.
Απόδειξη μέσω υπολογιστή
Κατά τη διάρκεια των δεκατιών του 1960 και του 1970, ο Γερμανός μαθηματικός Heinrich Heesch ανέπτυξε μεθόδους χρήσης του υπολογιστή, στην έρευνα για μια απόδειξη. Είναι αξιοσημείωτο το γεγονός ότι ήταν ο πρώτος που χρησιμοποίησε την εκκένωση για να αποδείξει το θεώρημα, η οποία αποδείχθηκε να είναι σημαντική στο αναπόφευκτο τμήμα της απόδειξης του Appel - Haken. Επίσης, επέκτεινε την ιδέα της ελάττωσης και, μαζί με τον Ken Durre, ανέπτυξε ένα τεστ στον υπολογιστή για το σκοπό αυτό. Δυστυχώς, σε αυτό το κρίσιμο σημείο, δεν ήταν σε θέση να προμηθευτεί τον απαραίτητο υπερυπολογιστή για να συνεχίσει το έργο του (Wilson 2002).[8]
Άλλοι συνέχισαν τις μεθόδους του και την υποβοηθούμενη από υπολογιστή προσέγγισή του. Καθώς άλλες ομάδες μαθηματικών αγωνίζονταν για να ολοκληρώσουν αποδείξεις, οι Kenneth Appel και Wolfgang Haken στο Πανεπιστήμιο του Ιλλινόις, ανακοίνωσαν στις 21 Ιουνίου 1976 ότι είχαν αποδείξει το θεώρημα. Είχαν βοηθηθεί σε κάποιες αλγοριθμικές εργασίες από τον John A. Koch (Wilson 2002).
Αν η εικασία των τεσσάρων χρωμάτων ήταν αναληθής, θα υπήρχε τουλάχιστον ένας χάρτης με το μικρότερο δυνατό αριθμό περιοχών, ο οποίος απαιτεί πέντε χρώματα. Η απόδειξη έδειξε ότι ένα τέτοιο ελάχιστο αντιπαράδειγμα δεν μπορεί να υπάρξει, μέσα από την εφαρμογή των δύο τεχνικών ιδεών (Wilson 2002∙ Appel & Haken 1989∙ Thomas 1998, σελ. 852-853).
.Ένα αναπόφευκτο σύνολο περιέχει περιοχές, έτσι ώστε ο κάθε χάρτης θα πρέπει να έχει τουλάχιστον μία περιοχή από αυτή τη συλλογή.
.Μία μειώσιμη διαμόρφωση είναι ένας σχηματισμός χωρών που δεν μπορούν να υπάρχουν σε ένα ελάχιστο αντιπαράδειγμα. Αν ένας χάρτης περιέχει μία μειώσιμη διαμόρφωση, τότε ο χάρτης μπορεί να μειωθεί σε ένα μικρότερο χάρτη. Αυτός ο μικρότερος χάρτης έχει την προϋπόθεση ότι αν μπορεί να χρωματιστεί με τέσσερα χρώματα, τότε ο αρχικός χάρτης μπορεί επίσης. Ο ανωτέρω ισχυρισμός δείχνει ότι αν ο αρχικός χάρτης δεν μπορεί να χρωματιστεί με τέσσερα χρώματα, τότε ούτε ο μικρότερος χάρτης μπορεί και έτσι και ο αρχικός χάρτης δεν είναι ο ελάχιστος.
Χρησιμοποιώντας μαθηματικούς κανόνες και διαδικασίες, οι οποίες βασίζονται σε ιδιότητες των μειώσιμων διαμορφώσεων, oι Appel και Haken βρήκαν ένα αναπόφευκτο σύνολο μειώσιμων διαμορφώσεων, αποδεικνύοντας κατά συνέπεια ότι, ένα ελάχιστο αντιπαράδειγμα στην εικασία των τεσσάρων χρωμάτων δεν θα μπορούσε να υπάρξει. Η απόδειξη τους μείωσε την απειρία των πιθανών χαρτών σε 1.936 μειώσιμες διαμορφώσεις (αργότερα μειώθηκαν σε 1.476), οι οποίες έπρεπε να ελεγχθούν μία προς μία από τον υπολογιστή, και απαιτήθηκαν πάνω από εκατό ώρες. Αυτό το ελαττώσιμο κομμάτι της εργασίας ελεγχόταν διπλά από διαφορετικά προγράμματα και υπολογιστές. Ωστόσο, το αναπόφευκτο κομμάτι της απόδειξης πιστοποιήθηκε σε περισσότερες από 400 σελίδες μικροδιαφανειών, οι οποίες έπρεπε να ελεγχθούν με το χέρι (Appel & Haken 1989).
Η ανακοίνωση των Appel και Haken αναφέρθηκε ευρέως από τα μέσα μαζικής ενημέρωσης ανά τον κόσμο, ενώ το τμήμα μαθηματικών στον Πανεπιστήμιο του Illinois χρησιμοποίησε μία ταχυδρομική σφραγίδα, η οποία δήλωνε «Τέσσερα χρώματα αρκούν». Την ίδια εποχή, η ασυνήθιστη φύση της απόδειξης – ήταν το πρώτο σημαντικό θεώρημα που είχε αποδειχθεί με εκτεταμένη βοήθεια ηλεκτρονικού υπολογιστή – και η πολυπλοκότητα του τμήματος της ανθρώπινης επαλήθευσης, προκάλεσε σημαντικές διαμάχες (Wilson 2002).
Στις αρχές της δεκαετίας του 1980, εξαπλώθηκαν φήμες για κάποιο σφάλμα στην απόδειξη των Appel – Haken. Ο Ulrich Schmidt στο RWTH Aachen εξέτασε την απόδειξη των Appel και Haken στη διπλωματική τους εργασία (Wilson 2002, σελ 225). Είχε εξετάσει περίπου το 40% του αναπόφευκτου τμήματος και βρήκε ένα σημαντικό σφάλμα στη μειωτική διαδικασία (Appel & Haken 1989). Το 1986, ο συντάκτης του περιοδικού Mathematical Intelligencer ζήτησε από τους Appel και Haken να γράψουν ένα άρθρο, απευθυνόμενοι στις φήμες περί σφαλμάτων στην απόδειξη τους. Απάντησαν ότι οι φήμες οφείλονταν στην «παρανόηση των [Schmidt] αποτελεσμάτων» και δεσμεύτηκαν με ένα λεπτομερές άρθρο (Wilson 2002, 225-226). Το μεγαλύτερο έργο τους, το Every Planar Map is Four – Colorable (Κάθε Επίπεδος Χάρτης είναι Τεσσάρων Χρωμάτων), είναι ένα βιβλίο όπου περιέχει μια ολοκληρωμένη και λεπτομερή απόδειξη (μαζί με ένα συμπλήρωμα μικροδιαφανειών με περισσότερες από 400 σελίδες), το οποίο δημοσιεύτηκε το 1989 και επεξηγούσε την ανακάλυψη του Schmidt και πολλά άλλα σφάλματα που βρέθηκαν από άλλους (Appel & Haken 1989).
Απλοποίηση και επαλήθευση
Από τη στιγμή που αποδείχθηκε το θεώρημα, αποτελεσματικοί αλγόριθμοι έχουν βρεθεί για χάρτες 4 χρωμάτων, που απαιτούν μόνο O (n2) χρόνο – ταξινόμηση φυσαλίδας που απαιτεί χρόνο (n2)- όπου 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).
Περίληψη των αποδεικτικών ιδεών
Η συζήτηση που ακολουθεί είναι μια περίληψη που βασίζεται στην εισαγωγή του βιβλίου των Appel και Haken, Κάθε επίπεδος χάρτης είναι τεσσάρων χρωμάτων (Appel & Haken 1989). Παρόλο που είχε σφάλματα, η αρχική, φιλόδοξη απόδειξη του θεωρήματος των τεσσάρων χρωμάτων παρείχε κάποια από τα βασικά εργαλεία που χρησιμοποιήθηκαν αργότερα για να το αποδείξουν. Η επεξήγηση εδώ, αναδιατυπώνεται με όρους της μοντέρνας θεωρίας γραφημάτων.
Το επιχείρημα του Kempel πάει ως εξής: Αρχικά, αν οι επίπεδες περιοχές που είναι χωρισμένες από το γράφημα, δεν είναι τριγωνικές, π.χ. δεν έχουν ακριβώς τρία άκρα στα σύνορα τους, μπορούμε να προσθέσουμε άκρα χωρίς να εισάγουμε νέες κορυφές, έτσι ώστε να κάνουμε κάθε περιοχή τριγωνική, συμπεριλαμβάνοντας την απεριόριστη εξωτερική περιοχή. Αν αυτό το τριγωνοποιημένο γράφημα μπορεί να χρωματιστεί, χρησιμοποιώντας τέσσερα ή λιγότερα χρώματα, τότε μπορεί να χρωματιστεί και το αρχικό γράφημα, καθώς ο ίδιος χρωματισμός ισχύει εάν αφαιρεθούν τα άκρα που προσθέσαμε. Έτσι λοιπόν αρκεί να αποδείξουμε το θεώρημα των τεσσάρων χρωμάτων για τριγωνοποιημένα γραφήματα, για να το αποδείξουμε για όλα τα επίπεδα γραφήματα, και χωρίς βλάβη της γενικότητας υποθέτουμε ότι το γράφημα είναι τριγωνικό.
Υποθέτουμε ότι v, e και f είναι ο αριθμός των κορυφών, των άκρων και των περιοχών. Αφού κάθε περιοχή είναι τριγωνική και κάθε άκρο ανήκει σε δύο περιοχές, έχουμε ότι 2e = 3f. Αυτό, μαζί με τον τύπο του Euler (Euler's formula) v − e + f = 2 μπορεί να χρησιμοποιηθεί για να δείξουμε ότι 6v − 2e = 12. Τώρα, ο βαθμός μιας κορυφής είναι ο αριθμός των άκρων που καταλήγουν σε αυτήν. Αν vn είναι ο αριθμός των κορυφών βαθμού n και D είναι ο μέγιστος βαθμός κάθε κορυφής,
\(6v - 2e = 6\sum_{i=1}^D v_i - \sum_{i=1}^D iv_i = \sum_{i=1}^D (6 - i)v_i = 12. \)
Αλλά από τη στιγμή που 12 > 0 και 6-i ≤ 0 για κάθε i ≥6, αυτό δείχνει ότι υπάρχει τουλάχιστον μία κορυφή βαθμού 5 ή μικρότερου.
Αν υπάρχει κάποιο γράφημα που απαιτεί 5 χρώματα, τότε υπάρχει ένα παρόμοιο ελάχιστο γράφημα, το οποίο απομακρύνοντας κάθε κορυφή γίνεται τεσσάρων χρωμάτων. Ας ονομάσουμε αυτό το γράφημα G. Το G δε μπορεί να έχει κορυφή βαθμού 3 ή μικρότερου, επειδή αν d(v) ≤ 3 (ο βαθμός της κορυφής να είναι μικρότερος ή ίσος από 3), μπορούμε να απομακρύνουμε τη v από το G, να χρωματίσουμε με τέσσερα χρώματα το μικρότερο γράφημα και μετά να επαναπροσθέσουμε τη v και να επεκτείνουμε το χρωματισμό με τέσσερα χρώματα σε αυτό, επιλέγοντας ένα χρώμα διαφορετικό από τους γείτονες της.
Ο Kempe επίσης έδειξε ορθά ότι το G δε μπορεί να έχει κορυφή βαθμού 4. Όπως και προηγουμένως, απομακρύνουμε αυτήν την κορυφή v και χρωματίζουμε με τέσσερα χρώματα τις κορυφές που απομένουν. Αν και οι τέσσερεις γείτονες της v έχουν διαφορετικά χρώματα, ας πούμε κόκκινο, πράσινο, μπλε και κίτρινο με σειρά που ακολουθεί τη φορά των δεικτών του ρολογιού, ψάχνουμε για ένα εναλλακτικό μονοπάτι κορυφών, που είναι χρωματισμένες με κόκκινο και μπλε, συνδέοντας τους κόκκινους και μπλε γείτονες. Ένα τέτοιο μονοπάτι ονομάζεται αλυσίδα του Kempe (Kempe chain). Μπορεί να υπάρχει μια αλυσίδα του Kempe που ενώνει τους κόκκινους και τους μπλε γείτονες και μπορεί να υπάρχει μια αλυσίδα του Kempe που να ενώνει τους πράσινους και τους κίτρινους γείτονες, αλλά όχι και τα δύο, καθώς αυτά τα δύο μονοπάτια αναγκαστικά θα τέμνονταν, και η κορυφή όπου θα τέμνονταν δεν θα μπορούσε να χρωματιστεί. Ας υποθέσουμε ότι είναι οι κόκκινοι και οι μπλε γείτονες που δεν δένονται μεταξύ τους. Ερευνήστε όλες τις κορυφές που είναι συνδεδεμένες στον κόκκινο γείτονα με κόκκινα-μπλε εναλλακτικά μονοπάτια, και μετά αντιστρέψτε τα χρώματα κόκκινο και μπλε σε όλες αυτές τις κορυφές. Το αποτέλεσμα εξακολουθεί να είναι έγκυρο, χρωματισμένο με τέσσερα χρώματα, και η v μπορεί τώρα να προστεθεί ξανά και να χρωματιστεί κόκκινη.
Αυτό αφήνει μόνο το ενδεχόμενο όπου το G έχει μια κορυφή βαθμού 5. Αλλά το επιχείρημα του Kempe ήταν λανθασμένο για αυτήν την περίπτωση. Ο Heawood πρόσεξε το λάθος του Kempe και επίσης παρατήρησε ότι αν κάποιος ήταν ικανοποιημένος με την απόδειξη ότι μόνο πέντε χρώματα απαιτούνται, θα μπορούσε να εξετάσει στα γρήγορα το παραπάνω επιχείρημα (αλλάζοντας μόνο ότι το ελάχιστο αντιπαράδειγμα απαιτεί 6 χρώματα) και να χρησιμοποιήσει τις αλυσίδες του Kempe στον βαθμό 5, για να αποδείξει το Θεώρημα των πέντε χρωμάτων.
Σε κάθε περίπτωση, για να αντιμετωπίσουμε την υπόθεση με αυτήν την κορυφή βαθμού 5, απαιτείται μια πιο περίπλοκη έννοια από την απομάκρυνση μιας κορυφής. Η μορφή του επιχειρήματος γενικεύεται, λαμβάνοντας υπόψη διαμορφώσεις, οι οποίες είναι συνδεδεμένα υπογραφήματα του G, με το βαθμό κάθε κορυφής (στην G) καθορισμένο. Για παράδειγμα, η περίπτωση που περιγράφηκε στη βαθμού 4 κορυφή, είναι ο σχηματισμός που αποτελείται από μία μονή κορυφή, που φέρει την ετικέτα πως έχει βαθμό 4 στη G. Όπως παραπάνω, είναι αρκετό να αποδείξουμε ότι αν η διαμόρφωση απομακρυνθεί και το γράφημα που παραμένει μπορεί να χρωματιστεί με τέσσερα χρώματα, τότε ο χρωματισμός μπορεί να μετατραπεί με τέτοιο τρόπο ώστε όταν η διαμόρφωση επαναπροστεθεί, ο χρωματισμός με τέσσερα χρώματα να μπορεί να επεκταθεί σε αυτό επίσης. Μια διαμόρφωση για την οποία αυτό είναι δυνατό, ονομάζεται μειώσιμη διαμόρφωση. Αν τουλάχιστον μια από ένα σύνολο διαμορφώσεων πρέπει να συμβαίνει σε κάποιο σημείο στο G, τότε αυτό το σύνολο ονομάζεται αναπόφευκτο. Το παραπάνω επιχείρημα ξεκίνησε δίνοντας ένα αναπόφευκτο σύνολο από πέντε διαμορφώσεις (μια μοναδική κορυφή με βαθμό 1, μια μοναδική κορυφή με βαθμό 2, ... , μια μοναδική κορυφή με βαθμό 5) και μετά προχώρησε για να δείξει ότι οι πρώτες 4 είναι μειώσιμες· το να επιδείξει ένα αναπόφευκτο σύνολο διαμορφώσεων όπου κάθε διαμόρφωση στο σύνολο είναι μειώσιμη, θα αποδείκνυε το θεώρημα.
Επειδή το G είναι τριγωνικό, ο βαθμός κάθε κορυφής σε μία διαμόρφωση είναι γνωστός και όλα τα άκρα που είναι εσωτερικά της διαμόρφωσης είναι γνωστά, ο αριθμός των κορυφών στο G που αντιστοιχεί σε μια δοσμένη διαμόρφωση είναι σταθεροποιημένος, και είναι ενταγμένα σε ένα κύκλο. Αυτές οι κορυφές σχηματίζουν τον δακτύλιο της διαμόρφωσης· μια διαμόρφωση με k κορυφές στον δακτύλιο της είναι μια διαμόρφωση k-δακτυλίου και η διαμόρφωση μαζί με τον δακτύλιο της καλείται δακτυλιωμένη διαμόρφωση. Όπως στις απλές περιπτώσεις παραπάνω, κάποιος μπορεί να απαριθμήσει όλους τους σαφείς χρωματισμούς με τέσσερα χρώματα του δακτυλίου· κάθε χρωματισμός που μπορεί να επεκταθεί χωρίς τροποποίηση σε ένα χρωματισμό της διαμόρφωσης καλείται αρχικά καλός. Για παράδειγμα, η διαμόρφωση με μοναδική κορυφή με τρεις η λιγότερους γείτονες θα ήταν αρχικά καλή. Γενικά, το περιβάλλον γράφημα πρέπει να επαναχρωματίζεται συστηματικά για να κάνει το χρωματισμό του δακτυλίου αρχικά καλό, όπως είχε γίνει στην περίπτωση παραπάνω, όπου υπήρχαν 4 γείτονες. Για μια γενική διαμόρφωση με ένα μεγαλύτερο δακτύλιο, απαιτούνται πιο πολύπλοκες τεχνικές. Εξαιτίας του μεγάλου αριθμού των σαφών χρωματισμών με τέσσερα χρώματα του δακτυλίου, αυτό είναι το πρωταρχικό βήμα που απαιτεί βοήθεια από ηλεκτρονικό υπολογιστή.
Τέλος, μένει να αναγνωριστεί ένα αναπόφευκτο σύνολο διαμορφώσεων που επιδέχονται μείωση με αυτή τη διαδικασία. Η πρωταρχική μέθοδος που χρησιμοποιήθηκε για να ανακαλύψει ένα τέτοιο σύνολο είναι η μέθοδος της αποφόρτισης (method of discharging). Η διαισθητική ιδέα που υπογραμμίζει την αποφόρτιση είναι να αντιληφθούμε το επίπεδο γράφημα ως ένα ηλεκτρικό δίκτυο. Αρχικά, θετική και αρνητική "ηλεκτρική φόρτιση" διανέμεται ανάμεσα στις κορυφές, έτσι ώστε το σύνολο να είναι θετικό.
Θυμηθείτε τον τύπο παρακάτω:
\( \sum_{i=1}^D (6 - i)v_i = 12. \)
Σε κάθε κορυφή έχει δοθεί μια αρχική φόρτιση από 6-deg(v) (6-βάθμια κορυφή). Τότε από μία "ρέει" το φορτίο με τη συστηματική αναδιανομή του φορτίου από μία κορυφή στις γειτονικές της, βασισμένο σε ένα σύνολο κανόνων, τη διαδικασία αποφόρτισης. Από τη στιγμή που η φόρτιση διατηρείται, κάποιες κορυφές έχουν ακόμα θετικό φορτίο. Οι κανόνες περιορίζουν τις πιθανότητες για διαμορφώσεις από θετικά φορτισμένες κορυφές, κι έτσι η απαρίθμηση όλων των πιθανών διαμορφώσεων δίνει ένα αναπόφευκτο σύνολο.
Όσο κάποιο μέλος του αναπόφευκτου συνόλου δεν δύναται να ελαττωθεί, η διαδικασία αποφόρτισης μετατρέπεται ώστε να το εξαλείψει (καθώς εισάγονται άλλες διαμορφώσεις). Η τελευταία διαδικασία αποφόρτισης των Appel και Haken ήταν εξαιρετικά πολύπλοκη και, μαζί με μια περιγραφή του αναπόφευκτου συνόλου διαμορφώσεων που προέκυπτε ως αποτέλεσμα, γέμισε έναν τόμο τετρακοσίων σελίδων, αλλά οι διαμορφώσεις που παρήγαγε μπορούσαν να ελεγχθούν μηχανικά έτσι ώστε να είναι μειώσιμες. Η επαλήθευση του τόμου που περιέγραφε το ίδιο το σύνολο αναπόφευκτων διαμορφώσεων, έγινε από ισότιμη κριτική, για μια περίοδο που διήρκησε αρκετά χρόνια.
Μια τεχνική λεπτομέρεια που δε συζητήθηκε εδώ αλλά που απαιτείται για να ολοκληρωθεί η απόδειξη είναι η απορρόφηση μειωσιμότητας (immersion reducibility).
Λανθασμένες αποδείξεις του θεωρήματος
Το θεώρημα των τεσσάρων χρωμάτων ήταν περιβόητο για την τον μεγάλο αριθμό λανθασμένων αποδείξεων που το αφορούσαν. Αυτό είχε ως αποτέλεσμα η εφημερίδα The New York Times να μην δημοσιεύσει αρχικά την είδηση για την απόδειξη των Appel-Haken, επικαλούμενη θέματα πολιτικής, από φόβο μήπως και αυτή η απόδειξη βρεθεί λανθασμένη.(Wilson 2002) Κάποιες από τις λανθασμένες αποδείξεις, όπως αυτή των Kempe και Tait που αναφέρθηκε παραπάνω, είχαν ελεγχθεί ενδελεχώς από την μαθηματική κοινότητα για περισσότερο από δέκα χρόνια, πριν εκτεθούν στη δημοσιότητα. Κάποιες άλλες, γραμμένες από ερασιτέχνες μαθηματικούς, δεν δημοσιεύτηκαν ποτέ.
Ο χάρτης (αριστερά) έχει χρωματιστεί με πέντε χρώματα, και είναι απαραίτητο να αλλαχθούν τουλάχιστον τέσσερις από τις δέκα περιοχές για να αποκτήσουμε ένα χρωματισμό με τέσσερα μόνο χρώματα (δεξιά).
Τα απλούστερα, αν και ανεπιτυχή, αντιπαραδείγματα αφορούσαν την κατασκευή χάρτη στον οποίο μια περιοχή εφάπτεται με όλες τις άλλες περιοχές. Σε αυτή την περίπτωση, για τον χρωματισμό των υπολοίπων περιοχών μπορούν να χρησιμοποιηθούν μέχρι τρία χρώματα, και κατά συνέπεια το πρόβλημα γίνεται πιο δύσκολο. Η απόδειξη του θεωρήματος των τεσσάρων χρωμάτων μας λέει ότι ακόμα και σε αυτή τη δύσκολη περίπτωση ο χάρτης είναι δυνατόν να χρωματιστεί με μόνο τέσσερα χρώματα.
Η τεχνική αυτή κατασκευής αντιπαραδείγματος αξιοποιεί την εξής γενική αρχή: υπάρχουν πολλοί χάρτες όπου αν τα χρώματα κάποιων περιοχών επιλεχθούν εκ των προτέρων, ο χάρτης είναι αδύνατον να χρωματιστεί με μόνο τέσσερα χρώματα. Κάποιος που κατασκευάζει ένα αντιπαράδειγμα μπορεί να μην λάβει υπόψη του ότι το χρώμα μιας περιοχής μπορεί να αλλαχθεί προκειμένου να ικανοποιηθούν οι συνθήκες του προβλήματος και ως εκ τούτου να παρουσιάσει το αντιπαράδειγμα ως έγκυρο.
Επίσης αυτά τα αντιπαραδείγματα συχνά δεν λαμβάνουν υπόψη τους ότι ο περιορισμός των χρωμάτων δεν είναι μια μεταβατική ιδιότητα: μια περιοχή θα πρέπει μόνο να χρωματιστεί διαφορετικά από τις περιοχές που συνορεύει άμεσα, όχι όμως και από περιοχές στις οποίες συνορεύει έμμεσα, δηλαδή σε αυτές που είναι γειτονικές σε αυτές που συνορεύει. Αν υπήρχε αυτός ο περιορισμός, τότε το πλήθος των απαιτούμενων χρωμάτων θα ήταν ίσο με το πλήθος των περιοχών.
Άλλα λανθασμένα αντιπαραδείγματα παραβιάζουν τα συμπεράσματα του θεωρήματος αλλάζοντας και αυτά κατ' ουσίαν τα χαρακτηριστικά του. Στις τεχνικές κατασκευής τους περιλαμβάνονται ο ορισμός περιοχής που αποτελείται από πολλά διαχωρισμένα μέρη, και η απαγόρευση σε περιοχές του ίδιου χρώματος να ενωθούν σε κάποιο σημείο.
Γενικεύσεις
Αν κάποιος ενώσει το μονά βέλη μαζί και τα διπλά βέλη μαζί, τότε δημιουργείται ένας τόρος με επτά περιοχές, που εφάπτονται αμοιβαία. Άρα λοιπόν απαιτούνται επτά χρώματα.
Αυτή η κατασκευή δείχνει τον τόρο, χωρισμένο το πολύ σε επτά περιοχές, καθεμία από τις οποίες εφάπτεται σε όλες τις υπόλοιπες.
Το θεώρημα των τεσσάρων χρωμάτων εφαρμόζεται όχι μόνο σε πεπερασμένης διάστασης επίπεδα γραφήματα, αλλά επίσης και σε άπειρης διάστασης γραφήματα, τα οποία μπορούν να σχεδιαστούν στο επίπεδο χωρίς να υπάρχουν διασταυρώσεις,και ακόμα γενικότερα σε γραφήματα άπειρης διάστασης (πιθανόν με ένα μη μετρήσιμο αριθμόκορυφών) για τα οποία κάθε πεπερασμένης διάστασης υπογράφημα είναι επίπεδο. Για να το αποδείξει κάποιος αυτό, μπορεί να συνδυάσει μια απόδειξη του θεωρήματος για πεπερασμένης διάστασης επίπεδα γραφήματα , με το θεώρημα του De Bruijn–Erdős (De Bruijn–Erdős theorem) που λέει ότι: αν κάθε πεπερασμένης διάστασης υπογράφημα ενός άπειρης διάστασης γραφήματος μπορεί να χρωματιστεί με k πλήθους χρώματα, τότε ολόκληρο το γράφημα μπορεί επίσης να χρωματιστεί με k πλήθους χρώματα (Nash-Williams 1967). Αυτό μπορεί να θεωρηθεί επίσης ως μια άμεση συνέπεια της συμπάγειας του θεωρήματος του Kurt Gödel για Λογική Πρώτης Τάξης, απλά εκφράζοντας τη δυνατότητα χρωματισμού ενός άπειρης διάστασης γραφήματος με ένα σύνολο λογικών τύπων.
Κάποιος θα μπορούσε επίσης να μεταφέρει το πρόβλημα του χρωματισμού και σε επιφάνειες, πέρα από το επίπεδο (Weisstein). Το πρόβλημα στη σφαίρα ή στον κύλινδροείναι ισοδύναμομε αυτό στο επίπεδο. Για κλειστές (προσανατολίσιμες ή μη προσανατολίσιμες) επιφάνειες με θετικό γένος (genus), ο μέγιστος αριθμός p των χρωμάτων που απαιτούνται εξαρτάται από τη χαρακτηριστική του Euler για επιφάνειες, βάση του τύπου:
\( p=\left\lfloor\frac{7 + \sqrt{49 - 24 \chi}}{2}\right\rfloor, \)
όπου οι αγκύλες που βρίσκονται πιο εξωτερικά υποδηλώνουν τη συνάρτηση του επιπέδου (floor function).
Εναλλακτικά, για μια προσανατολίσιμη επιφάνεια, ο τύπος μπορεί να δωθεί με όρους του γένους μιας επιφάνειας g:
\( p=\left\lfloor\frac{7 + \sqrt{1 + 48g }}{2}\right\rfloor (Weisstein). \)
Αυτή η κατασκευή δείχνει τον τόρο, χωρισμένο το πολύ σε επτά περιοχές, καθεμία από τις οποίες εφάπτεται σε όλες τις υπόλοιπες.
Ο P.J. Heawood, το 1890, θεώρησε πως ο παραπάνω τύπος (εικασία του Heawood) ισχύει. Η απόδειξη του έγινε το 1968 από τους Gerhard Ringel και J. T. W. Youngs. Η μοναδική εξαίρεση σε αυτόν τον τύπο είναι το μπουκάλι του Klein (Klein bottle), το οποίο έχει χαρακτηριστική του Euler 0 (ως εκ τούτου ο τύπος δίνει p = 7) και απαιτεί 6 χρώματα, όπως αποδείχθηκε από τον P. Franklin το 1934 (Weisstein).
Για παράδειγμα, ο τόρος έχει χαρακτηριστική του Euler χ=0 (και γένος g = 1) οπότε p = 7, άρα δεν χρειάζονται περισσότερα από 7 χρώματα για να χρωματίσεις οποιοδήποτε χάρτη που βρίσκεται πάνω σε έναν τόρο. Το πολύεδρο του Szilassi (Szilassi polyhedron) είναι ένα παράδειγμα που απαιτεί επτά χρώματα.
Μια λωρίδα του Möbius (Möbius strip) απαιτεί έξι χρώματα (Weisstein) όπως τα 1-επίπεδα γραφήματα (γραφήματα που σχεδιάζονται με το πολύ μία απλή διασταύρωση ανά άκρο) (Borodin 1984). Αν και τα άκρα και οι επιφάνειες ενός επίπεδου γραφήματος χρωματιστούν με τέτοιο τρόπο ώστε δύο γειτονικά άκρα, δύο γειτονικές όψεις, ή ένα ζευγάρι άκρου-όψης να μην έχουν το ίδιο χρώμα, τότε χρειάζονται και πάλι, το πολύ έξι χρώματα (Borodin 1984).
Δεν υπάρχει προφανής επέκταση του αποτελέσματος χρωματισμού σε τρισδιάστατες συμπαγείς περιοχές. Χρησιμοποιώντας ένα σύνολο από n εύκαμπτες ράβδους, μπορούμε να φροντίσουμε έτσι ώστε κάθε ράδβος εφάπτεται σε κάθε άλλη ράβδο. Το σύνολο τότε θα απαιτούσε n χρώματα, ή n+1 αν υπολογίσετε και τον κενό χώρο ο οποίος επίσης αγγίζει κάθε ράδβο. Ο αριθμός n μπορεί να θεωρηθεί ακέραιος, αυθαίρετα μεγάλος. Παραδείγματα όπως αυτό ήταν γνωστά στον Fredrick Guthrie το 1880 (Wilson 2002). Ακόμα και για κυβοειδή (cuboids), παράλληλα στον άξονα x (τα οποία θεωρούνται γειτονικά όταν μοιράζονται μια δισδιάστατη οριοθετημένη περιοχή) ένας απεριόριστος αριθμός χρωμάτων μπορεί να απαιτείται (Reed & Allwright 2008;Magnant & Martin (2011)).
Παραπομπές
Georges Gonthier (December, 2008). «Formal Proof---The Four-Color Theorem». Notices of the AMS 55 (11): 1382–1393.From this paper: Definitions: A planar map is a set of pairwise disjoint subsets of the plane, called regions. A simple map is one whose regions are connected open sets. Two regions of a map are adjacent if their respective closures have a common point that is not a corner of the map. A point is a corner of a map if and only if it belongs to the closures of at least three regions. Theorem: The regions of any simple planar map can be colored with only four colors, in such a way that any two adjacent regions have different colors.
Hud Hudson (May, 2003). «Four Colors Do Not Suffice». The American Mathematical Monthly 110 (5): 417–423.
Donald MacKenzie, Mechanizing Proof: Computing, Risk, and Trust (MIT Press, 2004) p103
F. G. (June 10, 1854), «Tinting Maps», The Athenaeum: 726.
Brendan D. McKay (2012). «A note on the history of the four-colour conjecture». arXiv:1201.2852.
De Morgan, Augustus (April 14, 1860), «Review of Whewell's "The Philosophy of Discovery"», The Athenaeum: 501–503. As cited by Wilson, John (1976), «New light on the origin of the four-color conjecture», Historia Mathematica 3: 329–330, doi:10.1016/0315-0860(76)90106-3.
Tait, P. G. (1880), «Remarks on the colourings of maps», Proc. R. Soc. Edinburgh 10: 729
Gary Chartrand and Linda Lesniak, Graphs & Digraphs (CRC Press, 2005) p221
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
