Math 2.1

(pour signaler une erreur monnerat@u-pec.fr)

Coloration de graphes : algorithme glouton

La coloration des sommets d'un graphe (sans boucle) consiste à affecter à tous les sommets de ce graphe une couleur de telle sorte que deux sommets adjacents ne portent pas la même couleur. Le nombre minimum de couleurs pour colorier un graphe s'appelle son nombre chromatique.

Soit $G = (V, E)$ un graphe simple. On note $χ (G)$ son nombre chromatique.

Bien que sa détermination constitue un problème souvent difficile, on peut en donner un encadrement relativement simple :

Une clique de $G$ est un sous graphe partiel complet. $χ (G)$ est nécessairement supérieur à l'ordre de n'importe quelle clique (pourquoi ?).
Le nombre chromatique est inférieur au plus grand des degrés plus 1. $χ (G) ≤ \underset{s ∈ V}{Max} \deg (s) + 1$ (pourquoi ?)

Vous allez implanter l'algorithme glouton. En voici un rappel :

Entrée : liste ordonnée V des n sommets d'un graphe G
         liste ordonnée C de couleurs
     
    Pour i variant de 1 à n
      v = V[i]
      couleur = la première couleur de C non utilisée par les voisins de v
      colorier(v, couleur)
    Fin pour

Rappel cet algorithme ne donne pas le nombre chromatique, mais une coloration possible.

Je mets à votre dispostion une archive dans laquelle se trouve des fonctions d'importations d'un graphe depuis un fichier texte, ainsi que des fonctions de dessins d'un graphe (orienté ou pas) qui utilise la bibliothèque graphique de l'iut. Voici le header :

#ifndef _GRAPHE_ 
#define _GRAPHE_
#include<stdio.h>
#include<graph.h>
 
typedef struct _graphe
{
	int ordre; /* nb de sommet */
	int **ma;  /* matrice d'adjacence */
	int oriente; /* 1 => oriente, 0 non oriente */
} * graphe ;
 
graphe  LireGraphe(FILE * stream); /* lecture depuis un fichier */
void AfficherGraphe(graphe G,FILE * stream);
graphe GrapheVide(int ordre);
graphe GrapheComplet(int ordre);
void DessinerGraphe(graphe G,int x,int y,int R,int r);
void DessinerGrapheCouleur(graphe G,int x,int y,int R,int r,couleur * cl);
couleur * ColorierGraphe(graphe G,int * nbc);
 
#endif

La seule fonction que vous devez écrire est la fonction ColorierGraphe qui renvoie le tableau (sa taille est le nombre de sommets du graphe) des couleurs de chaque sommet. nbc permet de savoir avec combien de couleurs le graphe a été colorié.

Le format d'importation d'un graphe est le suivant :

Redirigez l'entrée du programe avec un tel fichier :

./main < exemple.g

Testez avec le graphe d'exemple ci-dessus.
Testez avec le graphe complet d'ordre 5.
Testez avec le graphe de Petersen.
Testez avec la roue d'ordre 6.
Testez avec l'étoile d'ordre 6.

Dans tous les cas précédents, l'algorithme glouton donne t-il le nombre chromatique ?

Une application

A, B, C, D, E, F, G et H désignent huit poissons. Dans le tableau ci-dessous, une case rouge signifie que les poissons ne peuvent pas cohabiter dans un même aquarium.

	A	B	C	D	E	F	G	H
A
B
C
D
E
F
G
H

Quel nombre minimum d'aquariums faut-il ? Donnez une répartition des poissons dans les aquariums.

Travaux pratiques de Mathématiques