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 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 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 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 V_1 och V_3 ä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 V_1, V_2, V_3, V_4, V_5 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 V_1, V_2, V_3, V_4, V_5 är färgade korresponderande färger 1, 2, 3, 4, 5.
  3. Då tittar vi på undergrafen V_{13} 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 V_1 och V_3 inte avgränsar till varandra behöver vi till exempel endast byta färg på V_1 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 V_1 och V_3 ä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 V_{24} 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 V_2 eller V_4 och tilldela V den andra färgen, eller kan vi hitta en sekvens med linjer och områden mellan V_2 och V_4 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 V_1 och V_3.

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