Rappel : un arbre est un graphe connexe sans cycle. Un arbre couvrant d'un graphe connexe G à n sommets est un sous-graphe couvrant qui est un arbre. Combien d'arêtes possède un arbre à n sommets ? G a 5 sommets et arêtes { A , B } , { A , C } , { B , C } , { B , D } , { C , D } , { C , E } , { D , E } . Combien d'arêtes doit avoir un arbre couvrant ? Proposer un arbre couvrant de G .

Arbre couvrant et nombre d'arêtes

Facile Inspiré BAC France

Exercice inspiré d'un BAC France

Énoncé et solution adaptés au programme français. Voir crédits.

Énoncé

Rappel : un arbre est un graphe connexe sans cycle. Un arbre couvrant d'un graphe connexe $G$ à $n$ sommets est un sous-graphe couvrant qui est un arbre.

Combien d'arêtes possède un arbre à $n$ sommets ?
$G$ a 5 sommets et arêtes ${A, B}, {A, C}, {B, C}, {B, D}, {C, D}, {C, E}, {D, E}$ . Combien d'arêtes doit avoir un arbre couvrant ?
Proposer un arbre couvrant de $G$ .

Bloqué sur cet exercice ?

Léo peut t'expliquer pas à pas, en s'adaptant à ton niveau.

Demander à Léo

Exercice Terminé? 🎉

Validez votre réponse pour enregistrer votre progression et gagner des points

Algorithme de Prim — réseau électrique Retour au chapitre Chaîne de Markov à trois états : évolution et état stable

Arbre couvrant et nombre d'arêtes

Énoncé

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Arbre couvrant et nombre d'arêtes

Énoncé

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Valider votre réponse

Tu as vu 5 exercices aujourd'hui 🎯