Ipoteza lui Heawood

Conjectura lui Heawood , sau teorema Ringel-Yangs, oferă o limită inferioară a numărului de culori care sunt necesare pentru a colora un grafic pe o suprafață cu un anumit gen . Această limită se numește numărul cromatic de suprafață sau numărul Heawood. Pentru suprafețele din genul 0, 1, 2, 3, 4, 5, 6, 7, ..., numărul necesar de culori este 4, 7, 8, 9, 10, 11, 12, 12, .... A000934 ,.

Ipoteza a fost formulată în 1890 de Percy John Heawood și dovedită în 1968 de Gerhard Ringel și Ted Youngs . Un caz, și anume sticla Klein nedirecționată , este o excepție de la formula generală. A fost nevoie de o abordare complet diferită pentru problema mult mai veche a găsirii numărului de culori necesare unui plan sau sferă și a fost rezolvată în 1976 de Wolfgang Haken și Kennthe Appel ( teorema în patru culori). Pe o sferă, limita inferioară este ușor de găsit, iar pe suprafețele de gen superior, este ușor să găsești o limită superioară și s-a dovedit în lucrarea scurtă originală a lui Heawood, care conține formularea conjecturii. Cu alte cuvinte, pentru a demonstra teorema lui Ringel, Youngs și alții au trebuit să construiască exemple extreme pentru fiecare gen de suprafață g = 1,2,3,.... Dacă g = 12s + k, genul suprafeței se împarte în 12 cazuri conform la restul k = 0 ,1,2,3,4,5,6,7,8,9,10,11. Anii în care au fost soluționate douăsprezece cauze și cine le-a hotărât:

Ultimele șapte excepții separate au fost rezolvate:

Declarație oficială

Percy John Heawood a presupus în 1890 că, pentru un anumit gen g > 0, numărul minim de culori necesare pentru a colora orice gen dat al acelui gen desenat pe o suprafață orientabilă (sau, echivalent, pentru a colora orice partiție a suprafeței în pur și simplu conectate). domenii) este dat de

unde este funcția de podea .

Heawood însuși credea că a demonstrat egalitatea în formulă, dar deja un an mai târziu Heffter [1] a subliniat inexactități în demonstrația lui Heawood, astfel încât inegalitatea a rămas. Heffter însuși a dovedit egalitatea pentru . Ca urmare, afirmația că egalitatea este valabilă în formula Heawood a devenit cunoscută sub numele de conjectura Heawood despre colorarea hărților [2]

Înlocuind genul cu caracteristica Euler , obținem o formulă care acoperă atât cazurile orientabile, cât și cele neorientabile,

După cum au arătat Ringel și Youngs, această egalitate este valabilă pentru toate suprafețele, cu excepția sticlei Klein . Philip Franklin a dovedit 1930 că o sticlă Klein are nevoie de maximum 6 culori, nu 7 așa cum spune formula. Graficul Franklin poate fi trasat pe sticla Klein în așa fel încât să se formeze șase regiuni de margine pe perechi, ceea ce arată că granița este exactă.

Limita superioară demonstrată în lucrarea originală a lui Heawood se bazează pe un algoritm de colorare lacom . Prin manipularea caracteristicii lui Euler, se poate demonstra că orice grafic încorporat într-o suprafață dată trebuie să aibă cel puțin un vârf cu un grad mai mic decât valoarea limită specificată. Dacă înlăturăm acest vârf și colorăm graficul rămas, numărul mic de muchii incidente cu vârful îndepărtat face posibilă adăugarea vârfului înapoi și a-i da o culoare fără a crește numărul de culori necesare. În sens invers, demonstrația este mai complicată, arătând că în toate cazurile (cu excepția sticlei Klein) poate fi încorporat într-o suprafață un grafic complet cu numărul de vârfuri egal cu un număr dat de culori.

Exemplu

Pentru torus , g = 1, astfel încât χ = ​​​​0. Astfel, după cum urmează din formulă, orice diviziune a torusului în regiuni poate fi colorată în șapte culori. Figura prezintă o partiție a torusului, în care fiecare dintre cele șapte regiuni se învecinează cu fiecare altă regiune. Această împărțire arată că marginea de șapte culori este corectă pentru acest caz. Limitele acestei partiții formează o încorporare a grafului Heawood în tor.

Note

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

Literatură

Link -uri