Algorithmes de Kruskal et de Prim
L'arbre couvrant de poids minimum d'un graphe pondéré : l'algorithme de Kruskal (arêtes par poids croissant, refus de celles qui ferment un cycle), celui de Prim (croissance depuis un sommet), la justification gloutonne et l'unicité.
- 29 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Comprendre
Quelques cartes du deck
Arbre couvrant de poids minimum : de quoi s'agit-il ?
Voir la réponse
Arbre couvrant d'un graphe pondéré connexe dont la somme des poids des arêtes est la plus petite possible.
C'est la solution du câblage le moins cher qui relie tous les points. Il y en a parfois plusieurs, tous de même poids.
Six bâtiments A à F, liaisons possibles et coût : A-B 7, A-C 3, B-C 5, B-D 4, C-D 8, C-E 6, D-E 2, D-F 9, E-F 1. Quelle est la première arête que Kruskal refuse ?
- C-E (6)
- A-B (7)
- C-D (8)
- D-F (9)
Voir la réponse
C-E (6)
Dans l'ordre : E-F 1, D-E 2, A-C 3, B-D 4 et B-C 5 sont gardées. À C-E (6), C est déjà relié à E par B, D : refus. A-B, C-D et D-F seront refusées aussi, mais plus tard.
Kruskal trie les arêtes par poids … et refuse toute arête dont les deux extrémités sont déjà dans la ….
Voir la réponse
Kruskal trie les arêtes par poids croissant et refuse toute arête dont les deux extrémités sont déjà dans la même classe.
Deux extrémités dans la même classe sont déjà reliées par des arêtes gardées : l'arête ajoutée fermerait un cycle.
Algorithme glouton : de quoi s'agit-il ?
Voir la réponse
Stratégie qui construit une solution en faisant à chaque étape le choix qui paraît le meilleur sur le moment, sans jamais le remettre en cause.
Pour l'arbre couvrant minimum, ce choix local est prouvé optimal. Pour d'autres problèmes, il peut donner une solution correcte mais pas la meilleure.