Taxi ! - Collège Jean Jaurès (Calais)

Un taxi doit amener de toute urgence un passager à sa destination. Il se trouve dans une ville dont les rues peuvent être représentées par les arêtes d’un graphe. À chaque intersection, se trouve un feu, rouge ou vert permettant ou non le passage du taxi. Toutes les deux minutes, tous les feux changent de couleur instantanément (pas de orange). Chaque minute le taxi passe d’une rue à une rue adjacente si le feu entre elles est vert, sinon, il reste
sur place.
— Pour un graphe donné, quel chemin doit emprunter le taxi pour arriver le plus rapidement possible ? Combien de temps mettra-t-il ?
— Que ce passe-t-il avec d’autres choix de durée, ou de graphe ?
— Est-ce possible de trouver une configuration de feux initiale qui fait que le trajet le plus rapide soit l’un des trajets passant par le plus de rues ?