Graphes orientés et problèmes résolus avec des graphes
Lis des graphes orientés, compte des poignées de main et des matchs d'un championnat, et trouve le plus court trajet en transformant le problème en graphe.
📖 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 7
Conseils pour les adultes
Ce thème ne figure pas au programme français avant la Terminale (enseignement de spécialité, option mathématiques expertes : graphes). Ici, il s'agit d'une première approche, accessible dès le collège. Un graphe est un modèle pratique : les sommets sont des personnes, des villes ou des équipes, et les arêtes sont des relations (amitié, routes, matchs). Si la relation a un sens (« A a dépassé B »), on dessine une flèche : c'est un graphe orienté. Un sommet a alors un certain nombre de flèches qui partent et de flèches qui arrivent.
Problèmes classiques : les poignées de main dans un groupe de n personnes (chacune serre la main à chacune une seule fois), les matchs d'un championnat (chaque équipe joue contre chaque autre). La somme des degrés est le double du nombre d'arêtes, donc le nombre d'arêtes est la moitié de la somme des degrés ; pour n sommets tous reliés, on obtient n×(n − 1) ÷ 2.
Une erreur fréquente est de compter chaque arête deux fois. Une autre est de confondre les flèches qui partent et celles qui arrivent. Un problème de trajet se résout en comptant les arêtes de la plus courte chaîne.