Heawoods hypotese

Heawoods formodning , eller Ringel-Yangs-sætningen, giver en nedre grænse for antallet af farver, der er nødvendige for at farve en graf på en overflade med en given slægt . Denne grænse kaldes det overfladekromatiske tal eller Heawood-tallet. For overflader af slægten 0, 1, 2, 3, 4, 5, 6, 7, ... er det nødvendige antal farver 4, 7, 8, 9, 10, 11, 12, 12, .... A000934 ,.

Hypotesen blev formuleret i 1890 af Percy John Heawood og bevist i 1968 af Gerhard Ringel og Ted Youngs . Et tilfælde, nemlig den urettede Klein-flaske , er en undtagelse fra den generelle formel. En helt anden tilgang var nødvendig for det meget ældre problem med at finde antallet af farver, der kræves til et fly eller en kugle , og løst i 1976 af Wolfgang Haken og Kennthe Appel ( fire farvesætning ) . På en kugle er den nedre grænse let at finde, og på overflader af højere slægt er det let at finde en øvre grænse, og det blev bevist i Heawoods originale korte papir, der indeholder formodningens formulering. Med andre ord, for at bevise Ringels sætning, måtte Youngs og andre konstruere ekstreme eksempler for hver overfladeslægt g = 1,2,3,.... Hvis g = 12s + k, opdeles overfladens slægt i 12 tilfælde iflg. til resten k = 0 ,1,2,3,4,5,6,7,8,9,10,11. År, hvor 12 sager blev afgjort, og hvem afgjorde dem:

De sidste syv separate undtagelser er blevet løst:

Formel erklæring

Percy John Heawood formodede i 1890 , at for en given slægt g > 0, det mindste antal farver, der kræves for at farve enhver tegning på en orienterbar overflade af den slægt (eller tilsvarende for at farve enhver opdeling af overfladen i simpelt forbundne domæner) er givet af

hvor er gulvfunktionen .

Heawood mente selv, at han havde bevist ligheden i formlen, men allerede et år senere påpegede Heffter [1] unøjagtigheder i Heawoods bevis, så uligheden forblev. Heffter beviste selv ligheden for . Som et resultat blev udsagnet om, at lighed gælder i Heawood-formlen, kendt som Heawood-formodningen om farvning af kort [2]

Ved at erstatte slægten med Euler-karakteristikken får vi en formel, der dækker både orienterbare og ikke-orienterbare tilfælde,

Som Ringel og Youngs viste, gælder denne lighed for alle overflader undtagen Klein-flasken . Philip Franklin beviste 1930, at en Klein-flaske maksimalt har brug for 6 farver, ikke 7, som formlen siger. Franklin-grafen kan tegnes på Klein-flasken på en sådan måde, at der dannes seks parvise grænseområder, hvilket viser, at grænsen er nøjagtig.

Den øvre grænse, der er bevist i Heawoods originale papir, er baseret på en grådig farvealgoritme . Ved at manipulere Euler-karakteristikken kan det vises, at enhver graf, der er indlejret i en given overflade, skal have mindst et toppunkt med grad mindre end den specificerede grænseværdi. Hvis vi fjerner dette toppunkt og farver den resterende graf, gør det lille antal kanter, der falder ind på det fjernede toppunkt, det muligt at tilføje toppunktet tilbage og give det en farve uden at øge antallet af nødvendige farver. I den modsatte retning er beviset mere kompliceret, hvilket viser, at der i alle tilfælde (med undtagelse af Klein-flasken) kan indlejres en komplet graf med antallet af hjørner svarende til et givet antal farver i en overflade.

Eksempel

For torus er g = 1, således at χ = ​​0. Som det følger af formlen, kan enhver opdeling af torus i områder således farves i syv farver. Figuren viser en skillevæg af torus, hvor hver af de syv regioner grænser op til hver anden region. Denne opdeling viser, at den syvfarvede ramme er nøjagtig for dette tilfælde. Grænserne for denne partition danner en indlejring af Heawood-grafen i torusen.

Noter

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

Litteratur

Links