Femfärgssatsen

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

Femfärgssatsen beskriver att om man har en given plan graf, t.ex. 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

Man börjar med att koppla en plan graf G' 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 sträck 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 V'. Grafen V' kommer då att ha färre områden än G, vilket gör att vi kan genom induktion anta att V' kan bli färgad med som mest fem färger.

Bild 1. Plana grafen V' om V endast avgränsar till fyra områden.
Bild 2. Plana grafen V' om V1 och V3 ä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 V'.
  2. Vi döper nu de angränsande områdena i V' till V1,V2,V3,V4,V5 i medurs ordning kring V' (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 V1,V2,V3,V4,V5 är färgade korresponderande färger 1, 2, 3, 4, 5.
  3. Då tittar vi på undergrafen V13 till V' 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 V1 och V3 inte avgränsar till varandra behöver vi t.ex. endast byta färg på V1 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 V1 och V3 ä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 V24 till V' 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 V2 eller V4 och tilldela V den andra färgen, eller kan vi hitta en sekvens med linjer och områden mellan V2 och V4 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 V1 och V3.

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


Användningsområden

Eftersom Femfärgssatsen ges av fyrfärgssatsen, har inte satsen några direkta praktiska användningsområden.


Se även

Personliga verktyg