Problema celor 4 culori

O problema celebra în teoria grafurilor este problema celor patru culori. Ea este mentionata într-o scrisoare din 1852 adresata de catre matematicianul De Morgan lui sir William Hamilton unde se referea la o întrebarea pusa de studentul Francis Guthrie daca o harta oarecare se poate colora cu cel mult patru culori astfel încât orice doua tari care au o frontiera comuna si care nu se reduce la un punct sa aiba culori diferite. Raspunsul la aceasta problema a fost obtinut în 1976 cu ajutorul unor programe de calcul de catre Appel si Haken. Legat de aceasta problema s-a introdus numarul cromatic al unui graf neorientat ca fiind numarul minim de culori cu care se pot colora vârfurile sale astfel încât orice muchie sa aiba capetele diferit colorate.

Courtesy Open Web DesignThanks to Dubai Hotels