Six sites à relier, et huit liaisons possibles avec leur coût. L'arbre couvrant minimal retient le sous-ensemble le moins cher qui relie tout le monde.
Le graphe
| Liaison | Coût |
|---|---|
| A ... C | 2 |
| C ... E | 3 |
| A ... B | 4 |
| E ... D | 4 |
| B ... C | 5 |
| E ... F | 8 |
| B ... D | 10 |
| D ... F | 11 |
Six sommets : A, B, C, D, E, F.
Objectif
Dérouler Kruskal et donner le poids total de l'arbre obtenu, le nombre d'arêtes retenues, le nombre rejetées, et le poids de la première arête rejetée.
Rappels
Un arbre couvrant sur n sommets compte exactement n moins une arêtes. C'est le critère d'arrêt.
Pièges
Une arête est rejetée non pas parce qu'elle est chère, mais parce que ses deux extrémités sont déjà reliées par les arêtes déjà retenues.