Théorème des quatre couleurs

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