Algorithme de Kruskal

Graphe original
Questions
  1. Appliquer l'algorithme de Kruskal sur le graphe ci-contre pour obtenir un arbre couvrant minimum.
    Arbre couvrant minimum :
    Graphe résultat

    Étape 1

    On met toutes les arêtes dans une liste que l'on trie par ordre croissant et on crée un graphe résultat contenant l'ensemble des sommets.

    Graphe étape 1

    Liste des arêtes : BE(3), FG(3), CF(5), BF(5), CE(6), BG(7), CG(8), BD(10), AB(11), DG(12), AD(16), BC(17), DE(18), CD(19), AE(23), AF(25), EF(25), AG(29), DF(30).


    Étape 2

    On ajoute l'arête BE au graphe résultat.

    Graphe étape 2

    Liste des arêtes : FG(3), CF(5), BF(5), CE(6), BG(7), CG(8), BD(10), AB(11), DG(12), AD(16), BC(17), DE(18), CD(19), AE(23), AF(25), EF(25), AG(29), DF(30).


    Étape 3

    On ajoute l'arête FG au graphe résultat.

    Graphe étape 3

    Liste des arêtes : CF(5), BF(5), CE(6), BG(7), CG(8), BD(10), AB(11), DG(12), AD(16), BC(17), DE(18), CD(19), AE(23), AF(25), EF(25), AG(29), DF(30).


    Étape 4

    On ajoute l'arête CF au graphe résultat.

    Graphe étape 4

    Liste des arêtes : BF(5), CE(6), BG(7), CG(8), BD(10), AB(11), DG(12), AD(16), BC(17), DE(18), CD(19), AE(23), AF(25), EF(25), AG(29), DF(30).


    Étape 5

    On ajoute l'arête BF au graphe résultat.

    Graphe étape 5

    Liste des arêtes : CE(6), BG(7), CG(8), BD(10), AB(11), DG(12), AD(16), BC(17), DE(18), CD(19), AE(23), AF(25), EF(25), AG(29), DF(30).


    Étape 6

    On n'ajoute pas l'arête CE au graphe résultat car elle créerait un cycle.

    Graphe étape 6

    Liste des arêtes : BG(7), CG(8), BD(10), AB(11), DG(12), AD(16), BC(17), DE(18), CD(19), AE(23), AF(25), EF(25), AG(29), DF(30).


    Étape 7

    On n'ajoute pas l'arête BG au graphe résultat car elle créerait un cycle.

    Graphe étape 7

    Liste des arêtes : CG(8), BD(10), AB(11), DG(12), AD(16), BC(17), DE(18), CD(19), AE(23), AF(25), EF(25), AG(29), DF(30).


    Étape 8

    On n'ajoute pas l'arête CG au graphe résultat car elle créerait un cycle.

    Graphe étape 8

    Liste des arêtes : BD(10), AB(11), DG(12), AD(16), BC(17), DE(18), CD(19), AE(23), AF(25), EF(25), AG(29), DF(30).


    Étape 9

    On ajoute l'arête BD au graphe résultat.

    Graphe étape 9

    Liste des arêtes : AB(11), DG(12), AD(16), BC(17), DE(18), CD(19), AE(23), AF(25), EF(25), AG(29), DF(30).


    Étape 10

    On ajoute l'arête AB au graphe résultat.

    Graphe étape 10

    Liste des arêtes : DG(12), AD(16), BC(17), DE(18), CD(19), AE(23), AF(25), EF(25), AG(29), DF(30).


    Étape 11

    On a ajouté 6 arêtes ; comme il y a 7 sommets, on a terminé.

Afficher les réponses
Lancer un exercice similaire avec les mêmes paramètres
Lancer un exercice similaire avec des paramètres différents
Lancer un exercice différent
Télécharger le graphe au format GraphVIZ