Colorer un cycle
Sommaire
Objectif #
On va étudier la notion de coloration de graphes, qui permet de modéliser plusieurs phénomènes en informatique.
On veut colorer les sommets d’un cycle de manière à ce que deux sommets reliés par une arête soient toujours de couleurs différentes.
On cherchera d’abord le nombre de couleur minimale et comment l’obtenir de façon centralisé, c’est-à-dire si l’on voit tout le graphes. On prendra ensuite une perspective distribuée où le graphe représente un réseau. Chaque sommet représentera un ordinateur et il devra communiquer avec ses voisins pour choisir sa couleur. On expérimentera plusieurs méthodes, sur papier et sur ordinateur, en essayant de minimiser le nombre de mises à jour de la couleur.
Pour la partie expérimentale de ce projet nous fournissons le code suivant.
Équipe encadrante #
Équipe GOAL
Disponibilités #
À préciser.