COLORIAGE PROBLÈME DU

Ce sujet est traité dans les articles suivants :

1.  ALGORITHMIQUE

Écrit par : Philippe COLLARD, Philippe FLAJOLET

Dans le chapitre "Algorithmes combinatoires"  : … polynomialement approximable pour des distances vérifiant l'inégalité triangulaire. – Problème du *coloriage de graphes : La situation du problème du coloriage de graphes est différente de celle des deux cas précédents. On montre en effet que le problème de détermination d'un coloriage qui soit dans un rapport α de l'optimum est, pour α < 2, de… Lire la suite

2.  GRAPHES PARFAITS THÉORÈME FORT DES

Écrit par : Vincent BARRÉ

…  que deux conférences adjacentes (reliées par une arête) ne soient pas dans la même salle. *Une telle affectation est appelée une coloration et le nombre de couleurs est au moins égal au plus grand nombre W(G) de sommets de G deux à deux adjacents. Par exemple, un cycle (graphe dont les sommets sont reliés uniquement à… Lire la suite

3.  INFORMATIQUE ET VÉRITÉ MATHÉMATIQUE

Écrit par : Jean-Paul DELAHAYE

Dans le chapitre "Preuves mathématiques classiques avec ordinateur"  : … conjecture de Kepler – est le plus intéressant et concerne le fameux théorème des quatre couleurs. *Celui-ci affirme qu'il suffit de quatre couleurs pour colorier toute carte de telle façon que deux pays ayant une frontière commune ne portent jamais la même couleur. Ce résultat, conjecturé en 1852 par Francis Guthrie (1831-1899), fut démontré en… Lire la suite