Heawoods hypotes

Heawoods gissning , eller Ringel-Yangs teorem, ger en nedre gräns för antalet färger som behövs för att färga en graf på en yta med ett givet släkte . Denna gräns kallas ytkromatiskt tal eller Heawood-talet. För ytor av släktet 0, 1, 2, 3, 4, 5, 6, 7, ... är det nödvändiga antalet färger 4, 7, 8, 9, 10, 11, 12, 12, .... A000934 ,.

Hypotesen formulerades 1890 av Percy John Heawood och bevisades 1968 av Gerhard Ringel och Ted Youngs . Ett fall, nämligen den oriktade Klein-flaskan , är ett undantag från den allmänna formeln. Ett helt annat tillvägagångssätt behövdes för det mycket äldre problemet med att hitta antalet färger som behövs för ett plan eller en sfär , och löstes 1976 av Wolfgang Haken och Kennthe Appel ( fyrfärgssatsen )). På en sfär är den nedre gränsen lätt att hitta, och på ytor av högre genus är det lätt att hitta en övre gräns, och det bevisades i Heawoods ursprungliga korta papper som innehåller formuleringen av gissningen. Med andra ord, för att bevisa Ringels sats var Youngs och andra tvungna att konstruera extrema exempel för varje ytsläkte g = 1,2,3,.... Om g = 12s + k delar sig ytans släkt i 12 fall enl. till återstoden k = 0 ,1,2,3,4,5,6,7,8,9,10,11. År då tolv ärenden avgjordes och vem avgjorde dem:

De senaste sju separata undantagen har lösts:

Formellt uttalande

Percy John Heawood antog 1890 att , för ett givet släkte g > 0, det minsta antal färger som behövs för att färga en ritning på en orienterbar yta av det släktet (eller, på motsvarande sätt, för att färga en uppdelning av ytan i enkelt sammankopplade domäner) ges av

var är golvfunktionen .

Heawood själv trodde att han hade bevisat likheten i formeln, men redan ett år senare påpekade Heffter [1] felaktigheter i Heawoods bevis, så att ojämlikheten kvarstod. Heffter själv bevisade jämställdheten för . Som ett resultat blev påståendet att jämlikhet råder i Heawood-formeln känt som Heawood-förmodan om färgläggning av kartor [2]

Genom att ersätta släktet med Euler-karaktäristiken får vi en formel som täcker både orienterbara och icke-orienterbara fall,

Som Ringel och Youngs visade, gäller denna likhet för alla ytor förutom Klein-flaskan . Philip Franklin bevisade att en Klein-flaska behöver maximalt 6 färger, inte 7 som formeln säger. Franklin-grafen kan ritas på Klein-flaskan på ett sådant sätt att sex parvisa gränsområden bildas, vilket visar att gränsen är exakt.

Den övre gränsen som bevisats i Heawoods originaltidning är baserad på en girig färgalgoritm . Genom att manipulera Euler-karakteristiken kan det visas att varje graf som är inbäddad i en given yta måste ha minst en vertex med grad mindre än det angivna gränsvärdet. Om vi ​​tar bort denna vertex och färglägger den återstående grafen, gör det lilla antalet kanter som faller in på den borttagna vertexen det möjligt att lägga tillbaka vertexen och ge den en färg utan att öka antalet färger som krävs. I motsatt riktning är beviset mer komplicerat, vilket visar att i alla fall (med undantag för Klein-flaskan) kan en komplett graf med antalet hörn lika med ett givet antal färger bäddas in i en yta.

Exempel

För torus , g = 1, så att χ = ​​0. Således, som följer av formeln, kan varje uppdelning av torus i regioner färgas i sju färger. Figuren visar en skiljevägg av torus, där var och en av de sju regionerna gränsar till varannan region. Denna uppdelning visar att den sjufärgade kanten är korrekt för det här fallet. Gränserna för denna partition bildar en inbäddning av Heawood-grafen i torus.

Anteckningar

  1. ↑ Heffter, 1891 , sid. 477-508.
  2. ↑ Harari, 2003 , sid. 162.

Litteratur

Länkar