Wij moeten een praktische opdracht maken over het vierkleuren probleem, maar wij kunnen helaas niet veel vinden en als ik iets vind dan is het in het DUITS/ENGELS enz maar niet in het NEDERLANDS. Kunnen jullie me helpen?
Yvette
Leerling bovenbouw havo-vwo - dinsdag 18 december 2001
Antwoord
Helaas, toch maar even Engels leren? Misschien heb je hier iets aan:
Een van de bekendste graafproblemen stamt uit de 19de eeuw, het vierkleurenprobleem: Is elke landkaart met vier kleuren te kleuren?
Dit probleem werd door Tait omgezet in een graafprobleem, en in de loop der jaren werden verschillende oplossingen voorgesteld, die alle echter niet juist bleken te zijn. Pas in 1976 slaagden Appel en Haken er in een sluitend bewijs te leveren, maar wel met behulp van de computer, die een hoop case-checking voor zijn rekening nam.
Het vierkleurenprobleem lijkt vrij theoretisch, maar de oplossing ervan heeft geleid tot een schat aan methoden en technieken welke van groot praktisch belang blijken te zijn.
Zo kunnen problemen als het toewijzen van treinperrons, busplatforms, hotelkamers, vacantie-bungalows etc. worden gezien als het kleuren van de hoekpunten van een graaf. Het toewijzen van frequenties aan radio-stations en -- dezer dagen van groot belang -- aan mobiele telefoons, wordt eveneens gemodelleerd als een graafkleuringsprobleem.
Ook kan graafkleuring worden toegepast bij het opstellen van schoolroosters. Het maken van zo'n rooster is en blijft in het algemeen een berucht, lastig probleem, waarvoor het moeilijk is binnen redelijke tijd een voor iedereen optimale oplossing te vinden.
Grafen geven een gereedschap het probleem te modelleren en te visualiseren, en om deelproblemen snel op te lossen. De basis van de meeste pakketten ontwikkeld voor dit probleem berust op een methode (en stelling) uit 1916 van de Hongaar Konig over het kleuren van grafen.
Op onderstaande website kan je wel het een en 't ander vinden..., maar toch ook weer veel Engels... Het 'probleem' staat ook bekend als vierkleurenstelling.
