Aller au contenu
Théorie des graphes · L1

Leçon 3 sur 5

Les arbres et l'arbre couvrant minimal

Je sais caractériser les arbres, démontrer leurs propriétés principales et construire un arbre couvrant de poids minimal avec les algorithmes de Kruskal et de Prim.

  • 1 h 10
  • 4 exercices corrigés
  • QCM de 5 questions

À la fin de la leçon, vous saurez :

  • Définir arbre, forêt et feuille et connaître les caractérisations équivalentes d'un arbre
  • Démontrer qu'un arbre à n sommets a n − 1 arêtes et au moins deux feuilles
  • Définir un arbre couvrant et justifier son existence dans un graphe connexe
  • Appliquer les algorithmes de Kruskal et de Prim sur un graphe pondéré

Avant de commencer : Leçons 1 et 2 de ce cours (degrés, chaînes, cycles, connexité).

1Je découvre

Une ONG veut électrifier six villages d'une sous-préfecture de Haute-Guinée à partir d'un réseau de lignes basse tension. Les techniciens ont estimé, pour chaque paire de villages proches, le coût de construction d'une ligne directe (en millions de GNF, chiffres de l'étude, fictifs ici). Il n'est pas nécessaire que chaque village soit relié directement à tous les autres : il suffit que l'électricité puisse circuler de proche en proche.

Le directeur demande : quelles lignes construire pour que tous les villages soient reliés et que le coût total soit le plus faible possible ? Un stagiaire remarque qu'il ne faut surtout pas de boucle : une ligne qui fermerait un cycle serait une dépense inutile, puisque les villages concernés seraient déjà reliés.

Le réseau recherché est un arbre couvrant de poids minimal.

Qu'est-ce qu'un arbre en théorie des graphes, et comment trouver efficacement l'arbre couvrant le moins coûteux ?

La suite se lit avec votre compte Kharandi Université

La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.

Voir toutes les leçons de Théorie des graphes

Signaler une erreur dans cette leçon

Toutes les leçons de Théorie des graphes

Pose ta question à Karamö