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

Αυτή η σελίδα παρέχει μια σύντομη περίληψη της μια νέα απόδειξη των Τεσσάρων Χρωμάτων Θεώρημα και τέσσερις-χρωματισμός αλγόριθμο που βρέθηκαν από τον Neil Robertson, Daniel P. Sanders, Paul Seymour και Ρόμπιν Τόμας.

Ιστορία.

Το Χρώμα Τέσσερα το Πρόβλημα χρονολογείται από το 1852, όταν ο Francis Guthrie, ενώ προσπαθεί να χρωματίσει το χάρτη της κομητείες της Αγγλίας παρατηρήσει ότι τέσσερα χρώματα αρκούσε. Ζήτησε από τον αδελφό του Frederick αν είναι αλήθεια ότι κάθε χάρτης μπορεί να χρωματιστεί χρησιμοποιώντας τέσσερα χρώματα με τέτοιο τρόπο ώστε γειτονικές περιοχές (δηλαδή εκείνους που μοιράζονται ένα κοινό όριο τμήματος, δεν είναι μόνο ένα σημείο) να λάβετε διαφορετικά χρώματα. Frederick Guthrie, στη συνέχεια, ανακοινώνονται οι εικασίες να DeMorgan. Η πρώτη έντυπη αναφορά οφείλεται Cayley το 1878.

Ένα χρόνο αργότερα, η πρώτη “απόδειξη” από Kempe εμφανίστηκε. η ανακρίβεια επισημάνθηκε από Heawood 11 χρόνια αργότερα. Άλλη μια αποτυχημένη απόδειξη οφείλεται Tait το 1880, ένα κενό στο επιχείρημα επισημάνθηκε από Petersen το 1891. Απέτυχαν και οι δυο αποδείξεις, όντως, είχε κάποια αξία. Kempe ανακάλυψε αυτό που έγινε γνωστό ως Kempe αλυσίδες, και Tait βρεθεί μια ισοδύναμη διατύπωση των Τεσσάρων Χρωμάτων Θεώρημα όσον αφορά την 3-edge-coloring.

Η επόμενη σημαντική συνεισφορά προήλθε από Μπίρκοφ το έργο του οποίου επιτρέπεται Φράνκλιν, το 1922 για να αποδείξει ότι το χρώμα τέσσερα που η εικασία είναι αλήθεια για τους χάρτες με το πολύ 25 περιοχές. Ήταν, επίσης, χρησιμοποιείται από άλλα μαθηματικοί να κάνω διάφορες μορφές της προόδου στις τέσσερις το πρόβλημα του χρώματος. Θα πρέπει συγκεκριμένα να αναφέρω Heesch που ανέπτυξαν τα δύο κύρια συστατικά που απαιτούνται για την απόλυτη απόδειξη – αναγωγιμότητα και αποφόρτιση. Ενώ η έννοια της αναγωγιμότητας μελετήθηκε από άλλους ερευνητές, καθώς, φαίνεται ότι η ιδέα της απαλλαγής, ζωτικής σημασίας για την unavoidability μέρος της απόδειξης, είναι λόγω Heesch, και ότι ήταν αυτός που εικάζεται ότι ένα κατάλληλο ανάπτυξη αυτής της μεθόδου θα λύσει το Χρώμα Τέσσερα το Πρόβλημα.

Αυτό επιβεβαιώθηκε από Appel και Haken το 1976, όταν δημοσίευσε την απόδειξη των Τεσσάρων Χρωμάτων Θεώρημα [1,2].

Γιατί μια νέα απόδειξη

Υπάρχουν δύο λόγοι για τους οποίους ο Appel-Haken απόδειξη δεν είναι απόλυτα ικανοποιητική.

Μέρος των Appel-Haken απόδειξη χρησιμοποιεί έναν υπολογιστή, και δεν μπορεί να ελεγχθεί με το χέρι, και
ακόμη και το μέρος που υποτίθεται ότι είναι στο χέρι checkable είναι εξαιρετικά περίπλοκη και κουραστική, και απ ‘ όσο ξέρουμε, κανείς δεν το έχει ελέγξει στο σύνολό της.

Στην πραγματικότητα, έχουμε προσπαθήσει να εξακριβώσει την Appel-Haken απόδειξη, αλλά σύντομα σταμάτησε. Τον έλεγχο του υπολογιστή, θα όχι μόνο απαιτεί πολύ προγραμματισμό, αλλά επίσης inputing τις περιγραφές του 1476 γραφήματα, και αυτό δεν ήταν καν το πιο αμφιλεγόμενο μέρος της απόδειξης.

Αποφασίσαμε ότι θα ήταν πιο κερδοφόρο να λειτουργήσει τη δική μας απόδειξη. Έτσι κάναμε και ήρθε με απόδειξη και έναν αλγόριθμο που περιγράφονται παρακάτω.

Περίγραμμα της απόδειξης.

Η βασική ιδέα της απόδειξης είναι η ίδια όπως Appel και Haken. Μας παρουσιάζουν ένα σύνολο 633 “διαμορφώσεις”, και να αποδείξει το καθένα από αυτά είναι “αναχθούν”. Πρόκειται για μια τεχνική έννοια που υποδηλώνει ότι δεν υπάρχει διαμόρφωση με αυτό το κατάλυμα μπορεί να εμφανιστεί σε ένα ελάχιστο αντιπαράδειγμα των Τεσσάρων Χρωμάτων Θεώρημα. Μπορεί επίσης να χρησιμοποιηθεί σε έναν αλγόριθμο, για το αν μπορεί να μειωθεί η διαμόρφωση, εμφανίζεται σε ένα επίπεδο γράφημα G, τότε μπορεί κανείς να κατασκευάσει σε σταθερό χρόνο μικρότερο επίπεδο γράφημα G τέτοιο ώστε κάθε τέσσερις-χρωματισμός του G ” μπορεί να μετατραπεί σε μια τέσσερις-χρωματισμός του G σε γραμμικό χρόνο.

Είναι γνωστό από το 1913 ότι κάθε ελάχιστο αντιπαράδειγμα των Τεσσάρων Χρωμάτων Θεώρημα είναι εσωτερικά 6-συνδεδεμένο τριγωνισμού. Στο δεύτερο μέρος η απόδειξη θα αποδείξουμε ότι τουλάχιστον το ένα από τα 633 διαμορφώσεις εμφανίζεται σε κάθε εσωτερικό 6-συνδέεται ο τριγωνισμός (όχι απαραίτητα ένα ελάχιστο αντιπαράδειγμα στο 4CT). Αυτό ονομάζεται αποδεικνύοντας unavoidability, και χρησιμοποιεί την “απαλλαγή μέθοδος”, που προτάθηκε πρώτα από Heesch. Εδώ μας μέθοδος διαφέρει από εκείνη των Appel και Haken.

Κύρια χαρακτηριστικά γνωρίσματα της απόδειξης.

Επιβεβαιώνουμε μια εικασία του Heesch που αποδεικνύει την unavoidability, μπορεί να μειωθεί η διαμόρφωση μπορεί να βρεθεί στη δεύτερη γειτονιά “υπερφορτωμένος” vertex, αυτό είναι το πώς θα αποφευχθεί η “βύθιση” προβλήματα που είχαν μια σημαντική πηγή επιπλοκή για Appel και Haken. Αναπόφευκτη σύνολο έχει μέγεθος 633 σε αντίθεση με το 1476 κράτη σύνολο των Appel και Haken, και μας απαλλάσσει μέθοδος χρησιμοποιεί μόνο 32 απαλλαγή κανόνες, αντί των 300+ των Appel και Haken. Τέλος, παίρνουμε μια τετραγωνική αλγόριθμο τέσσερις-χρώματος επίπεδων γραφημάτων (που περιγράφεται αργότερα), μια βελτίωση σε σχέση με το quartic αλγόριθμος των Appel και Haken.

Διαμορφώσεις.

Κοντά τριγωνισμού είναι μη-null συνδεδεμένοι loopless αεροπλάνο γράφημα τέτοιο ώστε κάθε πεπερασμένη περιοχή έχει ένα τρίγωνο. Μια ρύθμιση παραμέτρων K αποτελείται από κοντά-τριγωνισμού G και ένα χάρτη g από το V(G) των ακεραίων με τις εξής ιδιότητες:

  • για κάθε κορυφή v, G\v έχει το πολύ δύο συνιστώσες, και εάν υπάρχουν δύο, τότε ο βαθμός β είναι g(v)-2,
  • για κάθε κορυφή v αν v είναι το περιστατικό με τον άπειρο περιοχή, τότε το g(v) ισούται με το βαθμό του v, και αλλιώς g(v) είναι μεγαλύτερη από το βαθμό του v, και σε κάθε περίπτωση, g(v)> 4,

Κ έχει δαχτυλίδι μεγέθους τουλάχιστον 2, όταν το δαχτυλίδι-το μέγεθος του K ορίζεται να είναι το άθροισμα του g(v))-deg(v)-1, αθροιστικά για όλες τις κορυφές v περιστατικό με το άπειρο περιοχή τέτοια ώστε το G\v είναι συνδεδεμένο.

Όταν ζωγραφίζει εικόνες από διαμορφώσεις χρησιμοποιούμε μια σύμβαση που εισήγαγε Heesch. Τα σχήματα των κορυφών αναφέρει η τιμή του g(v) ως εξής: στερεό μαύρο κύκλο σημαίνει ότι g(v)=5, μια τελεία (ή ό, τι εμφανίζεται στην εικόνα ως σύμβολο σε όλα) είναι g(v)=6, ένα κοίλο κύκλου, g(v)=7, ένα κοίλο τετράγωνο σημαίνει ότι g(β)=8, ένα τρίγωνο σημαίνει ότι g(v)=9, και ένα πεντάγωνο σημαίνει ότι g(v)=10. (Δεν χρειαζόμαστε κορυφές v με g(v)> 11, και μόνο μία κορυφή με g(v)=11, για τις οποίες δεν χρησιμοποιούμε ειδικό σύμβολο.) Στην παρακάτω εικόνα 17 633 μπορεί να μειωθεί διαμορφώσεις που εμφανίζονται με την ένδειξη της σύμβασης. Το σύνολο μπορούν να προβληθούν κάνοντας κλικ εδώ. (Ανατρέξτε στην ενότητα (3.2) από την εργασία μας [7] για την έννοια του “παχιά άκρα” και “μισό-άκρες” σε αυτές τις φωτογραφίες.)

Οποιαδήποτε ρύθμιση ισομορφικό με ένα από τα 633 διαμορφώσεις εκτίθενται στο [7] ονομάζεται μια καλή διαμόρφωση. Ας T είναι ένα τρίγωνο. Μια ρύθμιση παραμέτρων K=(G,g) εμφανίζεται στην T εάν το G είναι ένα εναγόμενο υπογράφημα του T, κάθε πεπερασμένη περιοχή του G είναι μια περιοχή του Τ και g(v) ισούται με το βαθμό του v στο T, για κάθε κορυφή v του G. Θα αποδείξουμε τις παρακάτω δύο δηλώσεις.

ΘΕΏΡΗΜΑ 1. Αν T είναι ένα ελάχιστο αντιπαράδειγμα των Τεσσάρων Χρωμάτων Θεώρημα, τότε δεν υπάρχει καλή ρύθμιση εμφανίζεται στην T.

ΘΕΏΡΗΜΑ 2. Για κάθε εσωτερικό 6-συνδεδεμένο τρίγωνο T, κάποια καλή ρύθμιση εμφανίζεται στην T.

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

Απαλλαγή κανόνες.

Ας T να είναι εσωτερικά 6-συνδεδεμένο τριγωνισμού. Αρχικά, κάθε κορυφή v έχει εκχωρηθεί μια χρέωση 10(6-deg(v)). Αυτό προκύπτει από τη φόρμουλα του Euler ότι το άθροισμα των χρεώσεων όλων των κορυφών είναι 120 * ειδικότερα, είναι θετική. Τώρα αναδιανείμει τις κατηγορίες σύμφωνα με τους ακόλουθους κανόνες, ως εξής. Όποτε T έχει ένα υπογράφημα ισομορφικό με ένα από τα γραφήματα στο σχήμα παρακάτω που ικανοποιεί ο βαθμός προδιαγραφές (για μία κορυφή v του κανόνα με το σύμβολο μείον, δίπλα v αυτό σημαίνει ότι ο βαθμός των αντίστοιχων κορυφών του T στην καλύτερη τιμή που καθορίζεται από το σχήμα του v, και κατ ‘ αναλογία για τις κορυφές με το συν δίπλα τους, ισότητα απαιτείται για κορυφές με κανένα σημάδι δίπλα τους) χρέωση μίας (δύο στην περίπτωση του πρώτου κανόνα) αποστέλλεται κατά μήκος της άκρης που επισημαίνονται με ένα βέλος.

Η διαδικασία αυτή ορίζει ένα νέο σύνολο των τελών με το ίδιο συνολικό ποσό. Δεδομένου ότι το συνολικό ποσό είναι θετικό, υπάρχει μία κορυφή v στο T, του οποίου επικεφαλής είναι θετική. Θα δείξουμε ότι μια καλή ρύθμιση παραμέτρων εμφανίζεται στη δεύτερη γειτονιά του v.

Αν ο βαθμός του v είναι το πολύ 6 ή, τουλάχιστον, 12, τότε αυτό μπορεί να δει κανείς αρκετά εύκολα με άμεση επιχείρημα. Για τις υπόλοιπες περιπτώσεις, ωστόσο, οι αποδείξεις είναι πολύ πιο περίπλοκη. Ως εκ τούτου, έχουμε γράψει τις αποδείξεις σε μια επίσημη γλώσσα, έτσι ώστε να μπορεί να ελέγχεται από έναν υπολογιστή. Κάθε βήμα που αυτές οι αποδείξεις είναι επαληθεύσιμα, αλλά οι αποδείξεις ίδιοι δεν είναι πραγματικά checkable με το χέρι, λόγω του μήκους τους.

Δείκτες.

Το θεωρητικό μέρος της απόδειξης που περιγράφεται στο [7]. 10 σελίδα έρευνα είναι διαθέσιμη on-line. Τα ηλεκτρονικά δεδομένα και τα προγράμματα που χρησιμοποιούνται για να βρίσκεται σε ένα ανώνυμο ftp server, αλλά ο διακομιστής έχει καταργηθεί. Τα ίδια αρχεία είναι τώρα διαθέσιμη από τη http://www.math.gatech.edu/~thomas/OLDFTP/τέσσερα/ και μπορεί να είναι εύκολα ορατό. Ένα ανεξάρτητο σύνολο προγραμμάτων γράφτηκε από Gasper Fijavz υπό την καθοδήγηση του Μπόγιαν Mohar.

Μια τετραγωνική αλγόριθμο.

Η είσοδος του αλγορίθμου θα είναι ένα αεροπλάνο τριγωνοποίηση G με n κορυφές. (Αυτό είναι, χωρίς απώλεια της γενικότητας, όπως και κάθε επίπεδο γράφημα μπορεί να είναι εντοπισμένοι σε γραμμικό χρόνο.) Η έξοδος θα είναι ένα χρωματισμό των κορυφών του G με τέσσερα χρώματα.

Εάν το G έχει το πολύ τέσσερις κορυφές χρώμα σε κάθε κορυφή ένα διαφορετικό χρώμα. Διαφορετικά, αν το G έχει μία κορυφή x του βαθμού k < 5, τότε το κύκλωμα C που την περιβάλλουν είναι ένα “k-ring”. Πάω να το k-ring ανάλυση παρακάτω. Διαφορετικά, το G έχει ελάχιστο βαθμό πέντε. Για κάθε κορυφή υπολογίζουμε την δαπάνη όπως εξηγήθηκε παραπάνω, και να βρει μια κορυφή v θετικό φορτίο. Αυτό προκύπτει από την απόδειξη του Θεωρήματος 2, που είτε μια καλή ρύθμιση παραμέτρων εμφανίζεται στη δεύτερη γειτονιά του β (τα οποία περίπτωση μπορεί να βρεθεί σε γραμμικό χρόνο), ή k-ring παραβιάζει τον ορισμό της εσωτερικής 6-σύνδεση μπορεί να βρεθεί σε γραμμικό χρόνο. Στην τελευταία περίπτωση θα πάμε στο k-ring ανάλυση που ακολουθεί, στην πρώτη περίπτωση θα ισχύουν αναδρομή σε ορισμένα μικρότερα γράφημα. Μια τέσσερις-χρωματισμός του G μπορούν στη συνέχεια να κατασκευαστεί από τα τέσσερα χρώματα της αυτό το μικρότερο γράφημα σε γραμμικό χρόνο.

Δίνεται k-ring R παραβιάζει τον ορισμό της εσωτερικής 6-σύνδεση με μια διαδικασία που αναπτύχθηκε από Μπίρκοφ μπορεί να χρησιμοποιηθεί. Εφαρμόζουμε αναδρομή σε δύο προσεκτικά επιλεγμένα subgraphs της Γ. σ. τέσσερις-χρωματισμός του G μπορούν στη συνέχεια να κατασκευαστεί από τα τέσσερα χρώματα των δύο μικρότερα γραφήματα σε γραμμικό χρόνο.

Η συζήτηση.

Θα πρέπει να αναφέρουμε ότι και οι δύο μας προγράμματα χρησιμοποιούν μόνο αριθμητική ακεραίων, και έτσι δεν χρειάζεται να ανησυχεί με στρογγυλοποίηση σφάλματα και παρόμοια κινδύνους αριθμητική κινητής υποδιαστολής. Ωστόσο, ένα επιχείρημα μπορεί να γίνει ότι οι “αποδείξεις” δεν είναι μια απόδειξη με την παραδοσιακή έννοια, επειδή περιέχει βήματα που δεν μπορεί ποτέ να ελεγχθεί από τον άνθρωπο. Ειδικότερα, δεν έχουμε αποδείξει την ορθότητα του μεταγλωττιστή θα καταρτίζονται τα προγράμματα μας, ούτε έχουμε αποδείξει το αλάθητο του υλικού τρέξαμε μας προγράμματα. Αυτά πρέπει να ληφθούν για την πίστη, και είναι πιθανώς μια πηγή σφάλματος. Ωστόσο, από πρακτική άποψη, η πιθανότητα ενός υπολογιστή σφάλματος που εμφανίζεται σταθερά με τον ίδιο ακριβώς τρόπο σε όλες τρέχει τα προγράμματά μας σε όλους τους compilers κάτω από όλα τα λειτουργικά συστήματα που μας προγράμματα είναι απειροελάχιστη σε σύγκριση με την πιθανότητα ανθρώπινου λάθους κατά την ίδια ποσότητα περίπτωση-ελέγχου. Εκτός από αυτό το υποθετικό ενδεχόμενο ενός υπολογιστή με συνέπεια να δίνει μια λανθασμένη απάντηση, το υπόλοιπο της απόδειξης μπορεί να επαληθευτεί με τον ίδιο τρόπο όπως τα παραδοσιακά μαθηματικές αποδείξεις. Θα παραδεχτώ, ωστόσο, ότι την επαλήθευση ένα πρόγραμμα υπολογιστή είναι πολύ πιο δύσκολο απ ‘ το να βλέπεις μια μαθηματική απόδειξη το ίδιο μήκος.

Αρχικά στο http://people.math.gatech.edu/~thomas/FC/

Leave a Comment

Your email address will not be published. Required fields are marked *