Graphes : ensembles dominants
Place des stations pour que chaque point de la carte soit couvert, et trouve le plus petit nombre possible de stations : le nombre de domination du 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 ».
- France : classe 12
- Russie : classe 7
- Iran : classe 12
Conseils pour les adultes
Ce thème ne figure pas au programme français ; c'est un prolongement de la logique et du dénombrement, qui se travaille sans prérequis autre que le calcul de CM2–6e. Imagine des distributeurs de billets placés à certains carrefours d'une ville. Chaque carrefour doit en avoir un ou être à une rue d'un carrefour qui en a un. On modélise cela par un graphe : les carrefours sont les sommets et les rues sont les arêtes. Un sommet de l'ensemble se domine lui-même et domine ses voisins.
Un ensemble de sommets est dominant si chaque sommet du graphe appartient à l'ensemble ou est voisin d'un sommet de l'ensemble. Le plus petit nombre de sommets d'un ensemble dominant est le nombre de domination, noté γ(G) ; un ensemble dominant de cette taille est un ensemble dominant minimum.
Minimal et minimum, ce n'est pas la même chose. Un ensemble minimal cesse d'être dominant si on retire n'importe quel sommet ; un ensemble minimum a le moins de sommets possible. Chaque sommet en domine au plus Δ + 1 (Δ est le plus grand degré) : pour n sommets, il en faut donc au moins n divisé par Δ + 1, arrondi à l'entier supérieur.