COLORIAGE PROBLÈME DU

Articles

• ALGORITHMIQUE

  • Écrit par Philippe COLLARD, Philippe FLAJOLET
  • 6 652 mots
  • 3 médias
  – 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 complexité comparable au problème général. Donc, moyennant la conjecture P ≠ NP, il n'existe pas d'algorithme polynomial permettant la détermination approchée du nombre chromatique d'un graphe dans un rapport inférieur à 2.

• APPEL KENNETH (1932-2013)

  • Écrit par Melinda C. SHEPHERD
  • 382 mots

  Le mathématicien américain Kenneth Appel apporta, avec son confrère Wolfgang Haken, la preuve du problème dit des quatre couleurs en 1976.

  Kenneth Ira Appel naît le 8 octobre 1932, dans le quartier new-yorkais de Brooklyn. Il étudie les mathématiques au Queens College de New York, où il décroche...

• GRAPHES PARFAITS THÉORÈME FORT DES

  • Écrit par Vincent BARRÉ
  • 708 mots

  Vous organisez un colloque dans lequel plusieurs conférences sont données simultanément (dans des salles différentes et à des horaires imposés par les orateurs) et vous cherchez à occuper le moins de salles possibles (car vous devez les louer). Une méthode permettant de réaliser un tel planning consiste...

• INFORMATIQUE ET VÉRITÉ MATHÉMATIQUE

  • Écrit par Jean-Paul DELAHAYE
  • 1 988 mots
  ... Le dernier cas de figure – qui nous ramènera à la 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...

• QUATRE COULEURS PROBLÈME DES

  • Écrit par Jean MAYER
  • 2 176 mots
  • 2 médias
  Onveut colorier une carte géographique tracée sur le plan (ou la sphère) de manière que deux régions voisines soient toujours de couleurs différentes. Précisons que chaque région est connexe (d'un seul tenant) et que deux régions voisines ont au moins une ligne frontière en commun. Dans ces conditions,...

Média