Femfärgssatsen

Från Wikipedia
Hoppa till: navigering, sök

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.

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.

Bevis genom motsägelse[redigera | redigera wikitext]

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.

Bild 1. Plana grafen om V endast avgränsar till fyra områden.
Bild 2. Plana grafen om och är sammankopplade med en linje.
  1. V måste vara kopplad till fem andra områden. Annars skulle V kunna färgas i den färg som inte används av de övriga områdena i .
  2. Vi döper nu de angränsande områdena i till i medurs ordning kring (se Bild 1). Om vi inte använder alla fem färger till dem kan vi självklart färglägga V med den oanvända färgen. Vi kan då anta att är färgade korresponderande färger 1, 2, 3, 4, 5.
  3. Då tittar vi på undergrafen till som består av de områden som bara är färgade med färgerna 1 och 3, samt de linjer som kopplar samman dem. Om och inte avgränsar till varandra behöver vi till exempel endast byta färg på till färg 3, vilket gör att vi kan färga V med färg 1 och därmed lösa problemet. Om det motsatta gäller, alltså att och är sammankopplade med en linje, kan vi hitta en sekvens med linjer och områden som kopplar samma dem, endast ritade med färgerna 1 och 3 (se Bild 2).
  4. Nu kollar vi på den andra undergrafen till som består av de områden som bara är färgade med färgerna 2 och 4, samt de linjer som kopplar samman dem. Genomför samma undersökning som ovan. Då kan vi antingen byta färg på den ena av eller och tilldela V den andra färgen, eller kan vi hitta en sekvens med linjer och områden mellan och som endast är ritade med färgerna 2 och 4.
  5. Det senare alternativet kan ej genomföras då denna sekvens skulle korsa sekvensen mellan och .

Detta innebär att det ursprungliga antagandet var felaktigt och grafen G kan färgas med endast fem färger.