Loading AI tools
Från Wikipedia, den fria encyklopedin
Femfärgssatsen beskriver att om man har en given plan graf, till exempel en karta över länder i Europa, kan man färga alla länder med endast fem olika färger utan att några avgränsande länder har samma färg.
Den här artikeln behöver källhänvisningar för att kunna verifieras. (2020-12) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. |
Femfärgssatsen ges indirekt från det starkare fyrfärgssatsen, men kan bevisas fristående relativt enkelt (se nedan). Satsen bevisades ursprungligen genom ett misslyckat försök att bevisa Fyrfärgssatsen 1879. År 1890 hittade Percy John Heawood ett fel i beviset och resultatet blev Femfärgssatsen. Fyrfärgssatsen bevisades 86 år senare med hjälp av datorer.
Man börjar med att koppla en plan graf till vår karta ovan. Där låter man varje land i kartan motsvaras av ett område (gestaltas här som en cirkel). Två områden kopplas samman med en linje om och endast om de motsvarande länderna delar en gräns (dock ej hörn).
Om vi då låter G vara den plana graf med minst antal områden, som inte kan färgas med fem färger. Om vi kan rita G så att inga streck kopplar samman två områden med samma färg, stämmer satsen och grafen kan inte ritas med fem färger.
Beviset använder Eulers sats (se Eulerkarakteristik) för att visa att det måste finnas ett område V som kopplas till fem andra områden eller färre. Det använder även det faktum att G är en plan graf, alltså att G ligger inbäddad i planet utan några korsade linjer.
Nu tar vi ut V och dess närliggande områden ur G och kallar denna graf för . Grafen kommer då att ha färre områden än G, vilket gör att vi kan genom induktion anta att kan bli färgad med som mest fem färger.
Detta innebär att det ursprungliga antagandet var felaktigt och grafen G kan färgas med endast fem färger.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.