Graphes en TES

Coloration d'un graphe

Nombre chromatique

I. Coloration d'un graphe: exemple et algorithme

a) Exemple:

Ci-dessous la carte de six pays imaginaires; on a colorié cette carte à l'aide de 6 couleurs différentes...

Problème :

Est-il possible de colorier la carte en respectant les contraintes suivantes ?

- utiliser le minimum de couleurs ;

- faire en sorte que deux pays ayant une frontière commune soient coloriés de deux couleurs différentes...

Solution :

Pour chercher un tel coloriage, on n'utilise pas de carte; on travaille sur le graphe associé.

'On commence par colorer le pays qui a le plus de pays frontaliers'

graphe et graphe coloré: 3 en gris ; 1 et 5 en rouge ; 2 et 4 en bleu

b) Algorithme :

Colorer un graphe c'est colorer les sommets de telle façon que deux sommets distincts et adjacents aient toujours des couleurs différentes.

Méthode : Algorithme de Welch-Powell ou algorithme glouton

1. Ranger les sommets par ordre décroissant de leurs degrés ;
   
2. Choisir une couleur ;
   
3. Affecter cette couleur au premier sommet de la liste non encore coloré ;
   
4. Suivre la liste en attribuant cette même couleur à tout sommet
   

• quin'est pas encore coloré ;
  
• et qui n'est pas adjacent à un sommet coloréavec cette couleur.

Continuer jusqu'à ce que la liste soit finie.

Si tous les sommets ne sont pas colorés, choisir une couleur qui n'est pas encore utilisée et recommencer les étapes 3 et 4 ;

Continuer tant que chaque sommet n'est pas coloré.

II. Graphes complets

• Lorsque chaque sommet est relié à chaque autre par une arête, le graphe est complet.

Exemples :

• Un graphe planaire est un graphe qui peut être représenté sur un plan, sans qu'aucune arête n'en croise une autre.

Les premiers circuits imprimés étaient moins fragiles quand le graphe du circuit était planaire.

• Soit G un graphe complet d'ordre p .

Si p est inférieur ou égal à 4, alors G est planaire ;
Si p est supérieur ou égal à 5, alors G n'est pas planaire.

• A l 'origine des graphes planaires, on trouve le théorème des 4 couleurs :
  

'Il est possible, en n'utilisant que quatre couleurs différentes, de colorer n'importe quelle carte de sorte que deux régions limitrophes reçoivent toujours deux couleurs distinctes.'

III. Nombre chromatique

Le nombre chromatique est le plus petit nombre de couleurs nécessaires pour colorer le graphe; notons le  .

• Deux sommets distincts et reliés par une arête doivent avoir des couleurs différentes; lorsque le graphe est complet d'ordre n, son nombre chromatique    est n.

• On peut donner des couleurs différentes aux sommets. Donc si le graphe a n sommets, alors     n .

• Si le plus grand degré d'un sommet est r, alors   r+1.
  

• Si on peut extraire d'un graphe, un sous-graphe complet d'ordre p, alors p  .

Dans notre exemple:

Du graphe associé à la carte, on peut extraire un sous-graphe d'ordre 3 (les sommets 3, 5 et 6 et leurs arêtes)

donc 3  
D'autre part, on a coloré le graphe à l'aide de 3 couleurs; donc   3.
On peut conclure :  = 3

Pour trouver le nombre chromatique  d'un graphe, on cherche

- un encadrement de 

- une coloration du graphe en p couleurs: on en déduit   p.

Le plus souvent, on peut en déduire la valeur de  ...

Il peut arriver que l'on trouve 3     4 ; dans ce cas, on ne peut pas donner  !

A vous de jouer!

Avancé
Exercice de maths (mathématiques) 'Graphes (2) - coloration d'un graphe (Niveau Terminale ES)' créé le 20-06-2008 par iza51 avec Le générateur de tests - créez votre propre test!
Voir les statistiques de réussite de ce test de maths (mathématiques)

1. Un examen comporte 6 options au choix. Chaque option se déroule sur une demi-journée; un candidat donné ne peut pas passer plus d'une option la même demi-journée. On cherche une organisation qui utilise le moins de demi-journées possibles, sachant qu'il y a des candidats inscrits en Sport (1), en Équitation (2) et Informatique (3); d'autres en Musique(4), Informatique (3) et Piscine (5) ; d'autres enfin en Danse (6) et Piscine (5).

Le graphe associé est

a) On peut extraire un sous-graphe d'ordre p = 354, et p est inférieur ou égal au nombre chromatique.

b) En étudiant les degrés des sommets, on peut affirmer que le nombre chromatique est inférieur ou égal à 345 .

c) Pour que chaque élève puisse passer toutes ses options, il est impératif d'organiser cet examen sur 534 demi-journées au minimum

2. Un musée est constitué de six salles numérotées de 1 à 6; le plan de ce musée est associé au graphe suivant dans lequel une arête représente une porte de communication entre deux salles .

a) Peut-on visiter chacune des salles du musée en passant une fois et une seule par chacune des portes ? ouinonon ne peut pas savoir

b) Peut-on visiter chacune des salles du musée en passant une fois et une seule par chacune des portes et en revenant au point de départ ? ouion ne peut pas savoirnon

c) Le conservateur du musée souhaite différencier chaque salle des salles voisines (c'est-à-dire accessibles par une porte) par la moquette posée sur le sol. Combien faut -il de moquettes au minimum pour réaliser ce souhait ? 243