diakitekaba
-
26 déc. 2012 à 12:20
cs_jopop
Messages postés1540Date d'inscriptionlundi 26 mai 2003StatutMembreDernière intervention 1 août 2013
-
27 déc. 2012 à 11:43
Bonjour
Tous les algorithmes distribués que l’on considèrera dans cette partie seront dans le modèle
LOCAL.
On suppose que le graphe G est un cycle orienté muni d’une m-coloration. Tout sommet u possède une variable c(u) appartenant de 0 a m-1 représentant la couleur du sommet u.
L’orientation est définie en u par les relations prédécesseurs et successeurs, notées respectivement Pred(u) et Succ(u).
Question
Comment on peut montrer qu’en une ronde il est possible de calculer pour G une 4-coloration si m = 6 en donnant l’algorithme correspondant.
Et en déduire qu’il est possible de calculer
une 3-coloration pour G en partie entier de 1/2log*m + 2 rondes
On suppose maintenant que G est un graphe possèdant une 1-orientation, définie par
la relation Père(u) pour tout sommet u, et toujours muni d’une m-coloration.