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 : AF(1), AE(2), EF(2), CG(2), AC(6), FG(6), AD(10), CD(10), CE(14), DE(15), CF(17), BC(19), BF(22), AB(23), EG(23), DG(28).


    Étape 2

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

    Graphe étape 2

    Liste des arêtes : AE(2), EF(2), CG(2), AC(6), FG(6), AD(10), CD(10), CE(14), DE(15), CF(17), BC(19), BF(22), AB(23), EG(23), DG(28).


    Étape 3

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

    Graphe étape 3

    Liste des arêtes : EF(2), CG(2), AC(6), FG(6), AD(10), CD(10), CE(14), DE(15), CF(17), BC(19), BF(22), AB(23), EG(23), DG(28).


    Étape 4

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

    Graphe étape 4

    Liste des arêtes : CG(2), AC(6), FG(6), AD(10), CD(10), CE(14), DE(15), CF(17), BC(19), BF(22), AB(23), EG(23), DG(28).


    Étape 5

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

    Graphe étape 5

    Liste des arêtes : AC(6), FG(6), AD(10), CD(10), CE(14), DE(15), CF(17), BC(19), BF(22), AB(23), EG(23), DG(28).


    Étape 6

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

    Graphe étape 6

    Liste des arêtes : FG(6), AD(10), CD(10), CE(14), DE(15), CF(17), BC(19), BF(22), AB(23), EG(23), DG(28).


    Étape 7

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

    Graphe étape 7

    Liste des arêtes : AD(10), CD(10), CE(14), DE(15), CF(17), BC(19), BF(22), AB(23), EG(23), DG(28).


    Étape 8

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

    Graphe étape 8

    Liste des arêtes : CD(10), CE(14), DE(15), CF(17), BC(19), BF(22), AB(23), EG(23), DG(28).


    Étape 9

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

    Graphe étape 9

    Liste des arêtes : CE(14), DE(15), CF(17), BC(19), BF(22), AB(23), EG(23), DG(28).


    Étape 10

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

    Graphe étape 10

    Liste des arêtes : DE(15), CF(17), BC(19), BF(22), AB(23), EG(23), DG(28).


    Étape 11

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

    Graphe étape 11

    Liste des arêtes : CF(17), BC(19), BF(22), AB(23), EG(23), DG(28).


    Étape 12

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

    Graphe étape 12

    Liste des arêtes : BC(19), BF(22), AB(23), EG(23), DG(28).


    Étape 13

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

    Graphe étape 13

    Liste des arêtes : BF(22), AB(23), EG(23), DG(28).


    Étape 14

    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