NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 08/12/2014

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

TOPOLOGIE

 

Débutants

Géométrie

QUATRE COULEURS

OUTILS

 

Glossaire

Géométrie

 

 

 

INDEX

 

Quatre couleurs

Graphes

Relation d'Euler

Nombre chromatique

Chaine de Kempe

 

Sommaire de cette page

>>> Approche

>>> Détermination du nombre chromatique

>>> Algorithme glouton

>>> Anglais

 

 

 

 

 

 

 

Théorèmes des quatre couleurs

Utilisation des graphes

 

Une carte colorée est équivalente (duale) à un graphe dont les sommets sont colorés.

Colorer un graphe c'est attribuer une couleur à chacun des sommets, chaque paire de sommets reliée par une arête étant de couleurs différentes.

La quantité minimale de couleur pour colorer le graphe est appelée nombre chromatique du graphe.

 

 

 

Approche

 

 

Prenez la carte des pays et donnez une capitale à chaque pays. Pays et capitales sont de même couleur. Si deux pays possèdent une frontière commune reliez les deux capitales. Alors le réseau des liens entre capitales, le graphe, avec ses sommets colorés est équivalent à la carte initiale en termes de coloration.

 



 

Exemple avec le graphe coloré pour l'Europe occidentale

 

Exemple de graphes analysés par Neil Roberston et al. en 1995.

Cet exemple montre la richesse du problème des quatre couleurs et, par là même, la complexité de la résolution.

 

 

Tous ces graphes sont équivalents

 

La représentation sous forme de régions de ce graphe. Forme duale du graphe en tétraèdre (en haut à droite). Quatre  couleurs sont nécessaires.

 

Représentations duales

 

 

Colorer un graphe et détermination de K

 

Comment procéder méthodiquement à la coloration de ce graphe et ainsi déterminer son nombre chromatique?

 

Algorithme de Welsh-Powell

 

Dans un premier temps, nous calculons le degré des sommets (quantité d'arêtes).

 

Nous ordonnons les sommets par ordre décroissant (tableau). Ordre quelconque pour les égaux.

 

La première couleur (bleue) est appliquée au premier sommet (B). Elle convient également à tout sommet non connexe à B et non connexes entre eux. Soit G.

 

La deuxième couleur (rouge) est appliquée au sommet suivant (F) et ses compatibles, ici A.

 

Etc.

Le nombre chromatique de ce graphe est égal à 4.

 


 

Voir Algorithme

 

 

Algorithme glouton (vulgairement: "bestial")

Colorer un sommet. Pour le sommet s suivant non colorié, prendre la première couleur dans la palette qui n'a pas été utilisée pour des sommets adjacents au sommet s. Si les couleurs de la palette sont épuisées, c'est qu'il faut y ajouter une couleur.

Cet algorithme ne produit pas la solution optimale.  Mais …

Si le degré maximal d'un des sommets est dmax, le maximum de couleurs nécessaires est d+1 ou moins. Ce qui donne une borne supérieure au nombre chromatique.

Anglais: greedy algorithm for coloring vertices

Voir Algorithme glouton de recherche de chemin optimum

 

 

English corner

 

*    The four-color problem (américain),

the four-colour problem (anglais),
the 4CT, or
the Gunthrie's problem:

 

Does every planar graph have chromatic number 4 or less?

 

*    The chromatic number is the minimum number of colors needed for a proper coloring.

 

*    A proper coloring of a graph is an assignment of colors to the vertices of the graph such that every two vertices connected by an edge must receive different colors.

 

Source: The Notorious Four-Color Problem by Jeremy L. Martin (Kansas)
 

 

 

 

 

 

Retour

Suite

*    Quatre couleurs – Introduction

*    Coloration des graphes et relation d'Euler

*    Quatre couleursIndex

Voir

*    Cinq pays

*    Couleurs

*    Démonstration

*    Énigme des carrés mitoyens

*    Graphe à 2 couleurs

*    Graphe de Delaunay

*    Indicateur d'Euler-Poincaré

*    Introduction à la topologie

*    Quadrichromie

*    TopologieGlossaire

*    TopologieIndex

DicoNombre

*    Nombre 4

Sites

*    Voir références

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Geometri/TopoQGra.htm