Kortmaler til firfarvesætningen
Uanset hvor kompliceret et kort er, er fire farver altid nok til at farvelægge det, så lande med fælles grænse aldrig har samme farve. Påstanden er så enkel, at et barn kan afprøve den med farveblyanter, men alligevel krævede det mere end et århundrede og en computer at bevise den. Mal selv et tilfældigt kort, se, hvilke grænser der giver konflikt, og se derefter tre metoder gøre det – fra en hurtig grådig regel, der nogle gange kræver en femte farve, til en backtracking-søgning, der altid klarer sig med fire. Vælg en farve, og klik på lande for at male dem; en grænse bliver rød, når to naboer har samme farve. Lande, der kun mødes i et hjørne, må gerne have samme farve. Eller lad computeren gøre det: Vælg en metode, og tryk på Løs for at se den arbejde, eller på Trin for at følge ét træk ad gangen. Færrest farver undersøger, om dette kort kunne klare sig med tre eller endda to farver. Nyt kort tegner et andet kort, og Vis naboerne tegner netværket af lande, der deler en grænse.
Sådan virker det
- Vælg antallet af lande, og tryk på Nyt kort, eller begynd med det viste kort.
- Vælg en farve, og klik på lande for at male dem; hold øje med røde grænser, hvor naboer er i konflikt.
- Vælg en metode, og tryk på Løs eller Trin for at se den farvelægge kortet, og tryk på Færrest farver for at se, hvor mange farver dette kort kræver.
Fra kort til grafer
Sæt en prik i hvert land, og forbind to prikker, når deres lande deler en grænse. Kortet bliver en graf, og at farvelægge kortet er det samme som at farve prikkerne, så forbundne prikker er forskellige. Fordi kort tegnes på et fladt ark, er disse grafer plane: De kan tegnes uden krydsende linjer. Lande, der mødes i et enkelt punkt, som fire kvadrater i et hjørne, er ikke naboer. Firfarvesætningen siger, at enhver plan graf kan farves med fire farver. Slå Vis naboerne til for at se grafen for det aktuelle kort.
Tre måder at farve på
Grådig farvning tager landene ét ad gangen, dem med flest naboer først, og giver hvert land den første farve, som dets naboer ikke har brugt. Den er hurtig, men kortsynet, og på nogle kort griber den til en femte eller endda sjette farve. DSATUR, der blev opfundet af Daniel Brélaz i 1979, vælger altid som det næste det land, hvis naboer allerede viser flest forskellige farver, hvilket som regel undgår den fælde. Backtracking prøver farverne på skift, og når et land ikke har flere tilbage, fortryder den sine seneste valg og prøver igen; den finder altid en farvning med fire farver, nogle gange efter at være gået tilbage mange gange.
Ofte stillede spørgsmål
Hvorfor er fire farver altid nok?
Ingen har fundet en kort begrundelse. Beviset af Kenneth Appel og Wolfgang Haken fra 1976 viste, at ethvert kort må indeholde en af 1.936 små konfigurationer, og at hver af dem kan fjernes og farvningen senere genskabes; at kontrollere dem alle tog mere end tusind timers computertid. Et enklere computerbevis af Neil Robertson, Daniel Sanders, Paul Seymour og Robin Thomas fra 1996 kræver 633 konfigurationer, og i 2005 verificerede Georges Gonthier et bevis fuldstændigt med bevisassistenten Coq.
Kræver nogle kort alle fire farver?
Ja. Fire lande, der hver rører de tre andre, som et land omgivet af en ring af tre andre, kræver fire. Mange kort klarer sig dog med tre, og Færrest farver finder ud af det for kortet på skærmen. Generelt at afgøre, om et kort kan farves med tre farver, er et svært problem, NP-komplet, selv om fire farver altid er nok.
Hvorfor bruger den grådige metode nogle gange fem farver?
Den farver hvert land én gang og ombestemmer sig aldrig. Et tidligt valg kan efterlade et senere land omgivet af alle fire farver, og den eneste udvej er en femte. Backtracking ville i stedet gå tilbage og ændre de tidligere valg.
Gælder sætningen på andre flader?
På en kugle, ja: Den er det samme som planen. På en torus, overfladen af en donut, kræver nogle kort syv farver, og syv er altid nok, som Percy Heawood viste. Hvis lande må bestå af flere adskilte dele, som en nation med kolonier, er fire farver ikke længere nok.
Bliver der sendt noget til en server?
Nej. Kortet, farvningsmetoderne og kontrollen kører i din browser. Dine indstillinger bliver i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor