QCM - Algorithme de Kruskal

QCM - Arbre couvrant de poids minimum (Kruskal)

Question 1. Un arbre couvrant d'un graphe connexe $G$ à $n$ sommets possède :

$n$ arêtes$n-1$ arêtes$n+1$ arêtes$2n$ arêtes

Question 2. L'algorithme de Kruskal pour trouver un arbre couvrant de poids minimum procède en :

Partant d'un sommet et ajoutant l'arête de poids minimum vers un sommet non visitéTriant les arêtes par poids croissant et ajoutant chaque arête si elle ne crée pas de cycleFaisant un parcours BFS depuis le sommet de plus petit degréRetirant les arêtes de poids maximum une par une

Question 3. Pour détecter efficacement si une arête crée un cycle dans Kruskal, on utilise :

Un parcours en profondeurUne structure Union-FindUne file de prioritéUn tri topologique

Question 4. La complexité de l'algorithme de Kruskal avec Union-Find sur un graphe à $n$ sommets et $p$ arêtes est :

$O(np)$$O(p \log p)$$O(np \log p)$$O(n + p)$

Question 5. L'opération Find dans Union-Find :

Renvoie le minimum d'un ensembleRenvoie le représentant d'un ensembleFusionne deux ensemblesRenvoie l'ensemble contenant un élément

Question 6. L'algorithme de Prim pour l'arbre couvrant minimum procède en :

Triant toutes les arêtes par poids croissantPartant d'un sommet et ajoutant l'arête de poids minimum reliant l'arbre à un sommet extérieurSupprimant les arêtes de poids maximumFaisant un parcours en largeur

Question 7. Si un graphe connexe a toutes ses arêtes de poids distincts, son arbre couvrant minimum est :

Non définiUniqueParmi exactement 2 arbres possiblesQuelconque

Question 8. L'union par rang dans Union-Find consiste à :

Fusionner les deux ensembles dans l'ordre alphabétiqueRattacher l'arbre de plus petite hauteur sous la racine de l'arbre de plus grande hauteurTrier les éléments par rangSupprimer les éléments de rang faible

Question 9. Un arbre couvrant de poids minimum d'un graphe $G$ :

Contient toujours l'arête de poids maximum de $G$Ne contient jamais l'arête de poids minimum de $G$Contient toujours l'arête de poids minimum de $G$A toujours $n$ arêtes

Question 10. La propriété de coupure (cut property) stipule que :

On peut couper n'importe quelle arête de l'arbreL'arête de poids minimum traversant une coupure appartient à un ACMToute arête de l'ACM peut être remplacéeL'ACM ne dépend pas des poids