Arbres et arbres couvrants
L'arbre comme graphe connexe sans cycle, ses caractérisations (n − 1 arêtes, une seule chaîne entre deux sommets), la forêt, la feuille, l'arbre enraciné et l'arbre couvrant d'un graphe connexe.
- 29 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Comprendre
Quelques cartes du deck
Arbre : de quoi s'agit-il ?
Voir la réponse
Graphe connexe et sans cycle.
Les deux conditions comptent : le graphe A-B, B-C, C-A, D-E n'est ni connexe ni sans cycle. À n sommets, un arbre a exactement n − 1 arêtes.
Un graphe connexe a 7 sommets et 7 arêtes. Est-ce un arbre ?
- Non, il contient un cycle : 7 arêtes, c'est une de trop
- Oui, puisqu'il est connexe, aucune autre condition n'est nécessaire
- Non, un arbre doit avoir autant d'arêtes que de sommets
- Oui, dès qu'on peut choisir une racine parmi ses sommets
Voir la réponse
Non, il contient un cycle : 7 arêtes, c'est une de trop
Un arbre à 7 sommets a 6 arêtes. Un graphe connexe qui en a 7 possède une arête de trop, donc un cycle. Choisir une racine est toujours possible et ne prouve rien.
Un arbre à n sommets a exactement … arêtes ; une forêt de n sommets formée de k arbres en a ….
Voir la réponse
Un arbre à n sommets a exactement n − 1 arêtes ; une forêt de n sommets formée de k arbres en a n − k.
Chaque arbre de la forêt a un sommet de plus que d'arêtes : en sommant sur les k arbres, il manque k arêtes.
Forêt : de quoi s'agit-il ?
Voir la réponse
Graphe sans cycle, connexe ou non : chacune de ses composantes connexes est un arbre.
Une forêt de n sommets formée de k arbres a n − k arêtes. Un arbre est le cas particulier k = 1.