Teorema celor cinci culori
Teorema celor cinci culori este un rezultat al teoriei graficelor , care afirmă că, având în vedere un plan împărțit în regiuni conectate (cum ar fi o hartă politică a regiunilor unui stat), acestea pot fi colorate folosind nu mai mult de cinci culori, astfel încât nu există două regiuni adiacente cu aceeași culoare. În mod similar, se afirmă că fiecare grafic plan poate fi colorat cu cinci culori, astfel încât două vârfuri adiacente să aibă o culoare diferită. A fost demonstrat la sfârșitul secolului al XIX-lea de Percy John Heawood .
Această teoremă este o consecință a teoremei mai puternice a celor patru culori , dar dovada acesteia din urmă este mult mai complexă și a fost obținută abia în 1976 de Kenneth Appel și Wolfgang Haken cu ajutorul unui computer.
Dovada lui Heawood se bazează pe o dovadă eronată a teoremei (atunci conjectura ) celor patru culori publicate în 1879 de Alfred Kempe ; unsprezece ani mai târziu, Heawood a găsit o eroare în ea, dar a reușit să o modifice pentru a demonstra teorema celor cinci culori. Se bazează pe o procedură de reducere, în care pornind de la o hartă atribuită, numărul de regiuni prezente este redus, fără a micșora numărul de culori necesare pentru a o colora; la sfârșitul procedurii, se obține o nouă hartă cu cinci sau mai puține regiuni, care poate fi evident colorată cu cinci culori.
În esență, există șase procese de reducere diferite; de exemplu, una dintre acestea este combinarea regiunilor înconjurate în întregime de alta în aceasta din urmă: dacă sunt disponibile cel puțin două culori, odată ce harta „redusă” a fost colorată, va fi posibil să alegeți o culoare diferită pentru prima regiune a doua . Două dintre aceste proceduri, totuși, necesită ca cel puțin cinci culori să fie disponibile și, prin urmare, nu pot fi aplicate pentru a demonstra teorema celor patru culori.
Bibliografie
- Keith Devlin, Unde merge matematica , Torino, Bollati Boringhieri , 1994, ISBN 88-339-1182-9 .
