NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 27/12/2015

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

>>> Nombre chromatique

>>> Amusement

 

 

 

 

 

 

 

NOMBRE CHROMATIQUE

 

Quantité de couleurs pour colorer une carte, un objet …

Définition et exemples.

 

 

 

Nombre chromatique

Nombre chromatique K: plus petit nombre de couleurs permettant de colorier tous les sommets d’un graphe sans que deux sommets adjacents du graphe soient de la même couleur.

 

Propriétés

Quadrilatère:            K = 2;

Triangle:                    K = 3;

Quadrilatère complet: K = 4.

 

Complet veut dire: avec toutes ses diagonales.

 

 

K = 2

                               

Rappel: un sommet ne doit pas être relié à un sommet de même couleur.

K = 3

 

 

Le double pentagone (en bas à droite) est le graphe de Petersen, un graphe souvent utilisé pour illustrer la théorie des graphes.

K = 4

Remarque importante: tous les graphes présentés ci-dessus sont planaires. Ils peuvent être représentés par un graphe sans croisement.

Exemples avec les trois derniers:

Le graphe ci-dessous ne peut pas être colorié avec trois couleurs (à gauche les verts se font face!). Résolution avec une quatrième couleur au centre. À droite, une représentation de la carte correspondante.

K = 5

Remarque importante: ce graphe n'est pas planaire. Voir Les trois maisons

 

 

Amusement: couleurs remplacées par des nombres

Le problème consiste à placer des nombres aux sommets, tels que la différence en valeur absolue soit supérieure à un nombre k.

Ici, l'exemple avec le graphe de Petersen (vu ci-dessus), en exigeant une distance k supérieure à 2. Cette illustration montre la solution optimale.

Voir Jeux et énigmes

 

 

 

 

 

 

Retour

Suite

*    Relation d'Euler

*    Chaine de Kempe

*    Quatre couleursIndex

Voir

*    Cinq pays

*    Coloration avec six ou plus de couleurs

*    Couleurs

*    Démonstration

*    Énigme des carrés mitoyens

*    Graphe à 2 couleurs

*    Indicateur d'Euler-Poincaré

*    Introduction à la topologie

*    La promenade des demoiselles de Lucas (résolution)

*    Quadrichromie

*    TopologieGlossaire

*    TopologieIndex

DicoNombre

*    Nombre 4

Sites

*    Voir Références

Cette page

http://villemin.gerard.free.fr/aMaths/Topologi/aaaGraph/Chromat.htm