Arbres et graphes planaires
Reconnais un arbre, compte les arêtes d'un arbre et d'un arbre couvrant, et compte les faces d'un graphe planaire avec la formule d'Euler.
📖 Commence ici : lis les étapes de la « Leçon » dans l’ordre (1, 2, 3 …) et réponds à chaque question. Ensuite, passe à l’« Entraînement ».
- Russie : classe 8
Conseils pour les adultes
Ce thème ne figure pas au programme français du collège ni du lycée général ; c'est un prolongement pour les élèves curieux, qui prépare les graphes de Terminale (mathématiques expertes). Un arbre est un graphe connexe sans cycle. Propriétés : il y a exactement une chaîne entre deux sommets quelconques ; un arbre à n sommets a exactement n − 1 arêtes ; un arbre qui a plus d'un sommet possède une feuille (un sommet de degré 1). Les arbres décrivent les arbres généalogiques, les tables des matières et les tournois à élimination directe.
Un arbre couvrant d'un graphe connexe est une partie de ce graphe qui contient tous les sommets et qui est un arbre. Pour en obtenir un à partir d'un graphe à S sommets et A arêtes, on retire A − (S − 1) arêtes, une dans chaque cycle.
Un graphe est planaire si on peut le dessiner sans que deux arêtes se croisent. Pour un graphe planaire connexe, la formule d'Euler est vraie : S − A + F = 2, où F est le nombre de faces, la face extérieure comprise. C'est un thème d'approfondissement.