CM2 Partie2

Question 1

Graphe pondéré

Answer 1

Graphe avec des poids sur les arêtes

Question 1

Arbre couvrant minimum

Answer 1

minimise la somme des poids des arêtes de cet arbre

Question 2

Arête sortante

Answer 2

une arête sortante est une arête qui part d’un sommet inclus dans l’arbre partiel et se dirige vers un sommet qui n’est pas encore inclus dans l’arbre partiel.

Question 3

arête bleue

Answer 3

L’arête sortante de poids minimal

Question 4

Arbre couvrant minimum
Construction par fragments

Answer 4

• correspondant au sous-
  graphe de l’arbre de poids minimum
• Version distribuée de l’algorithme de Kruskal
• Au maximum log2(n) phases

Question 5

Algorithme de Gallager-Humblet-Spira

Answer 5

• Chaque nœud est la racine de son propre fragment
• ID du fragment = ID de la racine

Question 6

Problème du coloriage d’un graphe

Answer 6

• Colorier tous les nœuds du graphe tel que deux sommets voisins n’ont pas la même couleur
• On cherche souvent à avoir un petit nombre de couleurs

Question 7

Coloriage glouton distribué

Answer 7

• Chaque nœud a un unique ID
• Algorithme partiellement synchrone
• Fonctionnement par rondes (non synchronisées sur un temps global)

Question 8

Coloriage glouton distribué
Terminaison

Answer 8

• Quand il n’y a plus de nœud indécis
• Un nœud ne sait pas si l’algorithme a terminé
• Il sait seulement s’il a terminé et si ses voisins ont terminé

Question 9

Coloriage glouton distribué
Complexité

Answer 9

• Au plus n rondes

Question 10

Coloriage glouton distribué
Nombre de couleurs

Answer 10

• au plus Δ + 1
• Δ = degré du graphe (max des degrés)

Question 11

Coloriage distribué d’un arbre

Answer 11

• Algorithme très simple mais lent
• Racine prend la couleur Cp=0 et envoie cette couleur à ses fils

Question 12

Coloriage distribué d’un arbre Terminaison

Answer 12

• Quand les feuilles choisissent leur couleur
• Mais les nœuds, autres que les feuilles, ne savent pas si l’algorithme a terminé

Question 13

Coloriage distribué d’un arbre Complexité
en temps

Answer 13

En temps :
* Proportionnel à la profondeur de l’arbre
* Profondeur de n pour des arbres déséquilibrés

Question 14

Coloriage distribué d’un arbre Complexité
en messages

Answer 14

• En messages :n-1 messages envoyés
• Nombre de couleurs : 2

Question 15

Coloriage distribué rapide d’un arbre

Answer 15

• Algorithme faiblement synchrone

Question 16

Coloriage distribué rapide d’un arbre Complexité

Answer 16

• Le nombre de bits / couleurs est diminué d’un facteur log2 à chaque ronde
• Le nombre de rondes est proportionnel à log2*n
• Log*n = nombre de fois où il faut appliquer le log à n avant d’obtenir une valeur<= 2
• n-1 messages envoyés à chaque ronde
• Nombre de couleurs : 6