16
May
2017

Četiri Boje Teorema

Originalni: The Four Color Theorem

Ova stranica daje kratak sažetak novi dokaz u Četiri Boje Teorema i četiri boje algoritam je našao pored Neil Robertson, Daniel P. Sanders,Paul i Seymour Robin Thomas.



Sadr:

  1. Povijest.
  2. Zašto novi dokaz?
  3. Obrisa od dokaz.
  4. Glavni karakteristika naše dokaz.
  5. Konfiguracije.
  6. Ispuštajući pravila.
  7. Savete.
  8. Ima kvadratnu algoritam.
  9. Rasprave.
  10. Reference.

Povijest.

Četiri Boje Problem datira 1852 kada Francis Guthrie, dok je pokušavao da boja mapi okruga Engleske primetio četiri boje bio dovoljan. Pitao me je njegov brat Frederick da li je to istina da li mapu može biti boje koristeći četiri boje u takvim način na koji blizu regionima (odnosno oni dijele granicu zajednički segment, ne samo tacke) dobiti različitim bojama. Frederick Guthrie onda komunicirali je pretpostavka da DeMorgan. Prvi odštampao reference je zbog Cayley 1878.

Godinu dana kasnije prvi dokaz’ Kempe se pojavio; svoje incorrectness je istakla Heawood 11 godina kasnije. Jos jedan propali dokaz je zbogTait u 1880; rupu u argument je istakla Petersen 1891. Oboje izneverio dokaza da li imaju neke vrednosti. Kempe što je otkrio postao poznat kao Kempe lance, i Tait našao ekvivalent formulacija Četiri Boje Teorema u smislu 3-ivice-boje.

Sledeći veliki doprinos došao iz Birkof čiji je rad dozvoljeno Franklin je 1922 dokazati da je u četiri boje nagađanje je li istina za karte sa najviše 25 regiona. To je takođe korišten od strane drugih matematičari da napravi razne oblike napredak u četiri boje problem. Trebali bi posebno spomenuo Heesch koji je razvio dvije glavne potrebni sastojci za krajnju dokaz – reducibility i napišem otpusne liste. Dok koncept reducibility je studirao za drugog istraživača kao pa, izgleda da ideja da vrši, presudno za unavoidability dio dokaz,je zbog Heesch, i da je on bio taj koji conjectured to pogodan razvoj ovo metoda će riješiti Četiri Boje Problem.

Ovo je potvrdio Appel i Haken 1976, kad su objavili njihov dokaz u Četiri Boje Teorema [1,2].

Zašto novi dokaz?

Postoje dva razloga zašto se Appel-Haken dokaz nije potpuno zadovoljavajući.

  • Dio Appel-Haken dokaz koriste kompjuterski, i ne mogu biti potvrđeno od ruku, i
  • čak i dio koji je navodno ruku checkable je izuzetno komplikovana i dosadno, a koliko znamo, niko to potvrdili u cijelosti.

Mi smo, u stvari, pokusao da potvrdi Appel-Haken dokaz, ali ubrzo je odustao. Proverava kompjuter dio ne samo da bi potrebno mnogo programiranje, ali također inputing opisa od 1476 tabele, i to je bio čak ni većina kontroverzni dio dokaza.

Odlučili smo da će biti više profitabilan posao naše dokaz. Tako smo i došli sa dokaz i algoritam koji su opisao ispod.

Obrisa od dokaz.

Osnovna ideja dokaz je da je ista kao Appel i Haken je. Da smo izložba set 633 “konfiguracije”, i dokazati da je svaka od njih “reducible”. Ovo je tehnički koncept da implicira da ne podešavanja sa ovim vlasništvo može pojaviti u minimalno counterexample u Četiri Boje Teorema. Može se koristiti i u algoritam, ako reducible podešavanja izgleda u oštar grafikonu, onda može se izgraditi u stalnom vremena manji oštar grafikonu’ tako da je svaka četiri boje od G’ mogu pretvoriti u četiri boje od G u linearno vrijeme.

To je poznata još od 1913 da svaki minimalne counterexample u Četiri Boje Teorema je interno 6-povezan triangulacija. U drugi dio dokaza da smo dokazali da barem jedan od naših 633 konfiguracije izgleda da u svakom interno 6-povezan oštar triangulacija (ne mora da znači da je minimalni counterexample na 4CT). Ovo se zove dokazuje unavoidability, i koristi “otpušteni metoda”, prvi put predložio Heesch. Ovdje naš način razlikuje od onog od Appel i Haken.

Glavni karakteristika naše dokaz.

Da potvrdimo da je pretpostavka od Heesch to dokazuje unavoidability, reducible podešavanja može biti pronađen u drugom kraju od “prepun”tačka, ovo je kako smo izbjeći “potapanja” problemi koji su veliki izvor komplikacija za Appel i Haken. Naš neizbježno je postavio veličine 633 nasuprot 1476 član set Appel i Haken, i naša ispuštajući metod koriste samo 32 napišem otpusne liste za pravila, a 300+ od Appel i Haken. Napokon, smo dobili kvadratnu algoritam za četiri boje oštar grafikoni (opisao kasnije), poboljšanje preko quartic algoritamod Appel i Haken.

Konfiguracije.

U blizini-triangulacija je ne-nula povezan loopless avion grafikon tako da svaki ograničenom regionu je trougao. Je podešavanja “K” se sastoji od blizu-triangulacija G i mapi g od V(G) prirodnih brojeva sa sljedećim osobine:

  1. za svaki tačka v, N a v ima najviše dva komponente, i ako postoje dva, onda stepen v je g(posetioci)-2,
  2. za svaki tačka v, ako v nije incident sa beskonacno regionu, onda g(posetioci) jednako stepen v, i inače g(posetioci) veće nego stepen v, iu svakom slučaju g(posetioci)> 4,
  3. K ima prsten veličine bar 2, gde je prsten veličine o K je definiran biti sumu od g(posetioci)-deg(posetioci)-1, reci nad svim ugao v incident sa beskonacno regionu tako da G a v je povezan.

Kada slika konfiguracije mi koristimo konvencije predstavila Heesch. Oblike od tačke ukazuju vrijednost g(posetioci) kako slijedi: Solidno crni krug znači g(posetioci)=5, dot (ili, kako izgleda na slici dok ne simbol na sve) znači g(posetioci)=6, hollow krug znači g(posetioci)=7, hollow kvadrat znaci g(posetioci)=8, trougao znači g(posetioci)=9, i pentagon znači g(posetioci)=10. (Ne treba nam ugao v sa g(posetioci)> 11, i jedina tačka sa g(posetioci)=11, za koje smo ne koristiti specijalni simbol.) Na slici ispod 17 naše 633 reducible konfiguracijeprikazane koristeći naznačio konvencije. Cijeli set može biti protumačen klikom ovdje. (Zovemo (3.2) naše novine [7] za značenje “debela ivice” i “polu-ivice” u te slike.)



Bilo podešavanja isomorphic da jedan od 633 konfiguracije pokazao u [7] se zove dobrokonfiguraciji. Hajde T biti triangulacija. Podešavanja K=(G,g) pojavljuje u T ako G je izazvana subgraph T, svaki ograničene oblasti G je region T, i g(posetioci) jednako stepen v, u, T za svaki tačka v G. Smo dokazati nakon dve izjave.

TEOREMA 1. Ako T je minimalna counterexample u Četiri Boje Teorema, onda nema dobro podešavanja izgleda u T.

TEOREMA 2. Za svaki interno 6-povezan triangulacija T, neke dobro podešavanja pojavljuje u T.

Od iznad dva teoreme to znači da nema minimalne counterexample postoji, i tako 4CT je istina. Prvi, dokaz je potreban kompjuter. Drugi možete biti provjerio rukom za par meseci, ili, koristeći kompjuter, to bi mogao biti ovjeren za 20 minuta.

Ispuštajući pravila.

Hajde T biti interno 6-povezan triangulacija. U početku, svaka tačka v je dodijeljen odgovoran za 10(6-deg(posetioci)). Slijedi od Euler je formula da je suma od optužbe za sve ugao je 120; posebno, to je pozitivno. Sada delimo optužbe prema da je prati pravila, kao što slijedi. Kad god T ima subgraph isomorphic da jedan od grafikoni u lik ispod zadovoljavajuće stepen specifikacije (za tačka v pravilo sa minus potpiši na v ovo znaci taj stepen odgovarajući tačka od T je najviše vrijednostiodredi oblik v, i analogously za ugao sa plus znak pored njih; jednakost je potrebno za ugao sa nema znaka sljedeći da ih) optužbom za jedan (dva, u slučaju da je prvo pravilo) biti poslali uz ivice označene sa strijelom.



Ovaj postupak određuje novog seta optužbe sa istim ukupan iznos. Od ukupan iznos je pozitivne, postoji tačka v, u, T, čiji novi optužba je pozitivan. Mi pokazuju da je dobar podešavanja izgleda u drugom kraju od v.

Ako stupanj ” v ” je najviše 6 ili bar 12, onda to možeš biti viđen prilično je lako direktnim argument. Za preostalih slučajevima, međutim,dokazi su mnogo komplikovanije. Stoga, moramo napisao dokazi u formalnom jezik tako da oni mogu biti ovjeren kompjuter. Svaki pojedinac korak od ovih dokaza je ljudska-provjerena, ali dokaze sami nisu stvarno checkable ručno, zbog njihove dužinu.

Savete.

Teoretski dio naše dokaz je opisao [7]. 10 stranica istraživanje je dostupan na liniji. Kompjuter podatke i programe bio smješten na anonimniftp server, ali taj server je postepeno izbacen. Isto dosijei sada je dostupna od http://www.math.gatech.edu/~thomas/OLDFTP/četiri/ i mogu bitizgodno gleda. Nezavisna set programe je napisano do Gasper Fijavz pod vodstvom Bojan Mohar.

Ima kvadratnu algoritam.

Ulaz da algoritam će biti avion triangulacija G sa n ugao. (Ovo je bez gubitak generality, kao i bilo oštar grafikon može biti pratili u linearno vrijeme.) Izlaz ce biti boje od tačke od G sa četiri boje.

Ako G ima najviše četiri ugao boja svaka tačka drugačije boje. U suprotnom, ako G ima tačka x za diplomu k < 5, onda krug C okružuje to je `k-prsten’. Idi k-prsten analizu ispod. U suprotnom, G ima minimum stupanj pet. Za svaki tačka smo izračunati svoj optužba kao objasnio iznad, i naći je tačka v pozitivne optužba. Slijedi iz naše dokaz Teorema 2 to ili dobar podešavanja izgleda u drugom kraju od “v” (to tom slučaju to se može naći u linearno vrijeme), ili k-prsten kršenje definicija unutrašnje 6-veza može se naći u linearno vrijeme.U tom slučaju idemo u k-prsten analizu ispod, u bivšoj slučaj moramo prijaviti recursion da određene manje grafikon. Četiri boje od G mogu onda biti napravljeno od četiri boje ovo manji grafikon u linearno vrijeme.

Dao k-prsten R kršenje definicija unutrašnje 6-povezanost postupak je razvila Birkof mogu koristiti. Moramo prijaviti recursion dvije pažljivo biramo subgraphs G. četiri boje od G možete onda biti napravljeno od četiri farbanja dva manje u grafikoni linearno vrijeme.

Rasprave.

Treba da pomenemo da oba naša programe koristiti samo broj matematika, i trebamo biti zabrinuti za rundu-sa greške i slične opasnosti pokretnom računanja. Međutim, argument koji može da se pravi da je naš dokaz’ nije dokaz u tradicionalni smisla, jer sadrži korake da nikada ne može biti potvrđena od strane ljudi. Posebno, imamo nije dokazao korektnosti od toga – skupili smo našeg programa, niti smo dokazali jedinog boga, hardvera provjerili smo našeg programa. Ovih moraš da budeš odveden na vjere, i verovatno je izvor greška.Međutim, iz praktičnih tačke gledišta, šansu da kompjuterska greška koja se pojavljuje dosljedno na isti način na sve vodi našeg programa na sve compilersispod operativnih sistema koji nam programi trči je beskonačno mali u odnosu na priliku ljudskog grešaka tokom istu količinu svaki slučaj-provjeravam. Osim ovo hipotetski mogućnost kompjuter stalno daješ pogrešan odgovor, da ostatak naših dokaz može da bude potvrđeno u isti način kao tradicionalne matematički dokaze. Ustupamo je, međutim, daprovjera kompjuterski program je mnogo teže nego provjeravammatematički dokaz isto dužinu.

Priznanja.

Zahvalni smo Thomas Fowler, Christopher Carl i Heckman Barrett Zidove za njihovu pomoć sa priprema ovu stranicu. Naš posao je djelomično podržala Nacionalne Fondacija za Nauku.

Reference.

  1. K. Appel i W. Haken, Svaki oštar mapa je četiri colorable. Dio Mene. Ispuštajući, Illinois J. Matematike. 21 (1977), 429-490.
  2. K. Appel, W. Haken i J. Kocha, Svaki oštar mapa je četiri colorable. II dio. Reducibility, Illinois J. Matematika. 21 (1977), 491–567.
  3. K. Appel i W. Haken, Svaki oštar mapa je četiri colorable, Savremene Matematike. 98 (1989).
  4. Gd. Birkof, reducibility karte, Amera. J. Matematike. 35 (1913), 114-128.
  5. H. Heesch, Untersuchungen zum Vierfarbenproblem, Hochschulskriptum 810//b, Bibliographisches Institut, Mannheimu 1969.
  6. A. B. Kempe, Na geografska problem od četiri boje, Amera. J. Matematike., 2 (1879), 193-200.
  7. N. Robertson, D. P. Sanders, Policija Seymour i R. Thomas, Četiri boje teorema, J. Combin. Teorija Ser. B. 70 (1997), 2-44.
  8. N. Robertson, D. P. Sanders, Policija Seymour i R. Thomas, Novi dokaz u četiri boje teorema, Elektrona. Resa. Announc. Amera. Matematika. Brojke. 2 (1996), 17-25 (elektronske).
  9. T. L. Saaty, Trinaest šarene varijacije na Gatri je četiri boje nagađanje, Amera. Matematika. Mjesečna 79 (1972), 2-43.
  10. T. L. Saaty i C. P. Kainen, četiri boje problem. I napada osvajanja, Dover Publikacije, New York 1986.
  11. G. P. Tait, Note na teorema u geometrije položaj, Trans. Roy. Brojke. Edinburga 29 (1880), 657-660.
  12. H. Whitney i W. T. Tutte, Kempe lance i četiri boje problem”, u Studije u Grafikon Teoriji, II Dio (ed. R. D. Fulkerson), Iz Matematike. Br. od Amerika, 1975, 378-413.