[clos] exercice d'algo distribué Fermé

Question

Salut à tous! kelkun peut-il m'aider à résoudre cet exercice d'algo distribué? Merci de me répondre. 

Un ensemble de sommets S d&#8217;un graphe G est dit indépendant s&#8217;il n&#8217;y a pas d&#8217;arête de
G entre deux sommets quelconques de S. Un ensemble indépendant S est maximal si dans
G il n&#8217;y a pas d&#8217;autre ensemble indépendant dans G contenant strictement S.
On suppose que G possède un ensemble indépendant maximal S défini par une variable
booléenne M(u) &#8712; {0, 1} qui vaut 1 si et seulement si le sommet u &#8712; S.
Question 1. En supposant que G possède une 1-orientation, donner un algorithme qui en
une seule ronde construit une 3-coloration pour G.
Question 2. Donner une borne inférieure sur le nombre minimum de rondes pour calculer
un ensemble indépendant maximal dans un graphe à n sommets muni d&#8217;une 1-orientation.
Question 3. Généralisée la question 4 en proposant un algorithme permettant, à partir
d&#8217;un ensemble indépendant maximal et d&#8217;une k-orientation, de construire une (2k + 1)-
coloration

cs_Julien39 · Answer

Salut,

Non, on ne fera pas tes devoirs.

Sujet clos.

[clos] exercice d'algo distribué

1 réponse

Discussions similaires