Quiz Arbres Couvrants de Poids Minimal
Soit un graphe représenté sur l'image ci-contre.
Effectuez l'algorithme de Kruskal avec Union-Find.
Répondez aux 3 premières questions de ce quizz en lien avec cet exercice.
1) Combien d'arrêtes aura l'arbre recouvrant de poids minimum
6
2) Quel est l'état de la queue de priorité après son initialisation.
Donnez votre réponse sous la forme: 1-2/3-5/2-3/ ... /6-7 l'arrête 1-2 se trouve en tête de queue et l'arrête 6-7 se trouve en fin de queue dans cette exemple.
Dans l'expression d'une arrête, le plus petit sommet (numéro) doit être en premier comme dans l'exemple (7-6 n'est pas correct, 6-7 à la place)
4-7/1-6/6-7/2-4/1-4/1-2/2-5/2-3/1-7/3-6/3-5/4-5
3) Donnez les arrêtes figurant dans l'arbre recouvrant de poids minimum.
Donnez votre réponse sous la forme: 1-2/3-5/2-3/ ... /6-7 l'arrête 1-2 étant la 1ère arrête insérée dans l'arbre et l'arrête 6-7 la dernière.
Dans l'expression d'une arrête, le plus petit sommet (numéro) doit être en premier comme dans l'exemple (7-6 n'est pas correct, 6-7 à la place)
4-7/1-6/6-7/2-4/2-5/2-3
L'arbre recouvrant de poids minimum trouvé sur un graphe lorsque l'on utilise l'algorithme de Prim paresseux est différent de l'arbre de recouvrement trouvé sur un graphe lorsque l'on utilise l'algorithme de Prim stricte. On suppose partir du même sommet initial.
Faux
Soit un graphe représenté sur l'image ci-contre.
Effectuez l'algorithme de Prim paresseux.
Répondez aux 3 questions suivantes en lien avec cet exercice.
1) Combien d'éléments de la queue sont ignorés durant l'exécution de l'algorithme car les deux sommets de l'arrête sont déjà dans l'arbre recouvrant ?
2
2) Donnez les arrêtes figurant dans l'arbre recouvrant de poids minimum.
Donnez votre réponse sous la forme: 1-2/3-5/2-3/ ... /6-7 l'arrête 1-2 étant la 1ère arrête insérée dans l'arbre et l'arrête 6-7 la dernière.
Dans l'expression d'une arrête, le plus petit sommet (numéro) doit être en premier comme dans l'exemple (7-6 n'est pas correct, 6-7 à la place)
1-6/6-7/4-7/2-4/2-5/2-3
3) Donnez les arrêtes figurant dans la queue de priorité à la fin de l'exécution de l'algorithme.
Donnez votre réponse sous la forme: 1-2/3-5/2-3/ ... /6-7 l'arrête 1-2 étant l'arrête avec le poids le plus faible et 6-7 l'arrête avec le poids le plus fort.
Dans l'expression d'une arrête, le plus petit sommet (numéro) doit être en premier comme dans l'exemple (7-6 n'est pas correct, 6-7 à la place)
1-7/3-6/3-5/4-5
Soit un graphe représenté sur l'image ci-contre.
Effectuez l'algorithme de Prim stricte.
Donnez l'état de la queue de priorité après l'itération où l'on ajoute l'arrête 4-2 à l'arbre de recouvrement.
Donnez votre réponse sous la forme: 1-2;6;2/1-4;5;4/...
L'arrête 1-2 étant l'arrête avec le poids le plus faible et 6-7 l'arrête avec le poids le plus fort.
Dans l'expression d'une arrête, le plus petit sommet (numéro) doit être en premier comme dans l'exemple (2-1 n'est pas correct, 1-2 à la place).
Le chiffre entre les 2 points virgule est le poids de l'arrête et le chifre après le deuxième point-vrigule est le numéro du sommet utilisé pour stocker la paire <noeud, arrête> dans la queue de priorité.
2-5;7;5/2-3;8;3