Le feu à la forêt - Lycée Montdory (Thiers)

Prenons un graphe à n sommets. En combien d’étapes minimum et maximum (en fonction de n), pouvons-nous mettre le feu sur tous les sommets sachant que, à chaque étape :
- le feu se propage à tous les sommets adjacents aux sommets déjà enflammés
- on peut allumer un feu supplémentaire sur l’un des sommets non enflammé.
Différents types de graphes sont à étudier : les lignes, les graphes étoilés, les arbres.