Coloration des graphes

Coloration des graphes

COLORATION DES CARTES GEOGRAPHIQUE 

La coloration des cartes géographiques consiste à donner une couleur à chaque pays (où région) à condition que deux pays frontaliers ne soient pas porteurs de la même couleur.
II. Théorème des quatre couleurs 1. énoncé du théorème (Appel et Haken 1976)
Toute carte géographique est coloriable avec quatre couleurs sans que deux régions frontalières ne soient colorées de la même manière
D’une autre façon tout graphe planaire est coloriable en quatre couleurs, car toute carte géographique est représentable comme un graphe planaire.
La preuve de ce théorème est très compliquée. Elle consiste en une réduction à un certain nombre de graphes (plus de 1000) pour lequel le théorème a été prouvé à l’aide d’un calcul par ordinateur.

Historique

L’histoire de ce théorème commence en 1852 avec un étudiant du professeur de mathématique « De Morgan » à l’University College (Londres) , cet étudiant a dit à son professeur : « si une figure est divisée de quelque manière que ce soit, et si on colorie les morceaux de telle sorte que, chaque fois qu’ils ont une ligne frontalière, leurs couleurs soit distinctes, il va falloir 4 couleurs mais pas plus », et le 23 octobre de la même année Augustus De morgan a envoyé une lettre à monsieur William Rowan Hamilton “ professeur au Trinty College (Dublin) ” , il l’a informé par cette lettre de la remarque de son étudiant et il lui a posé la question suivante : « peut-on imaginer une figure nécessitant une cinquième couleur ? » il lui a dit « si 4 régions on deux à deux une ligne frontalière, trois d’entre elles enclavent la quatrième et empêche n’importe quelle cinquième de la toucher, si ceci était vrais, quatre couleurs seraient toujours suffisantes… ».Nous verrons que cette dernière affirmation, dont la démonstration consiste par ailleurs la seule vraie contribution de De Morgan au problème des quatre couleurs, repose sur une assez grossière erreur de raisonnement.Quant à Hamilton, obsédé qu’il était par son invention de quaternions, il répondit à De Morgan : « il est peut probable que je regarde bientôt votre problème de ‘quaternion ’ de couleur ».Puis l’affaire reste stationnaire jusqu’à ce que, en 1878, Arthur Cayley découvre à son tour le problème et lui donne une existence officielle en le posant à la communauté scientifique, dont deux notes parues l’une à la société mathématique de Londres, l’autre à la société géographique. Quant à l’étudiant de De Morgan qui avait découvert la propriété, son identité ne fut révélée qu’en 1880, grâce à une note du physicien Frederick Gurthrie au Proceeding of the Royal Society of Edinburgh :
« Il y a environ 30 ans, alors que je suivais les cours du professeur de De Morgan, mon frère, Francis Guthrie, qui venait d’en sortir (et qui est maintenant professeur de mathématiques à l’université Sud-Africaine, cap ), me fit remarquer que le plus grand nombre de couleurs nécessaires au coloriage d’une carte en évitant de colorier pareillement deux régions linéairement frontalières est quatre

Table des matières

Introduction
Chapitre 1 : Rappel sur les graphes
I. Première notions
1. Définition d’un graphe
2. Graphe simple
3. Degré d’un sommet
4. Graphe orienté
5. Graphe non orienté
II. Graphe planaire
1. Définition
2. Exemple
3. Vocabulaire
III. Matrice associée à un graphe
1. Matrice d’incidence sommet-arc
2. Matrice d’incidence sommet-sommet
Chapitre 2 : Coloration des graphes
I. Coloration des sommets d’un graphe
1. Définition
2. Ensemble stable
3. Nombre chromatique
4. Domaines d’applications
5. Algorithme de Welsh et Powell
 Sur les graphes
 Sur la matrice d’adjacence d’un graphe
II. Coloration des arêtes d’un graphe
1. Définition
2. L’indice chromatique d’un graphe
3. L’algorithme de welsh-powell
Chapitre 3 : Coloration des cartes géographiques
I. Définition
II. Théorème des quatre couleurs
1. Enonce du théorème
2. Historique
III. Exemple : coloration de la carte d’Ouazzane
Chapitre 4 : Gestion des examens
I. Introduction
II. Méthodes d’initialisation
III. Exemple : Organisation des examens de la session du printemps à la FST de Fès

Télécharger le rapport complet