Asie – juin 2003
Dans la ville de GRAPHE, on s’intéresse aux principales rues permettant de relier différents lieux ouverts au public, à savoir la Mairie (M), le Centre commercial (C), la Bibliothèque (B), la Piscine (P) et le Lycée (L). Chacun de ces lieux est désigné par son initiale. Le tableau ci-dessous donne les rues existant entre ces lieux :
X
X
P
X
X
X
X
M
X
X
L
X
X
X
C
X
X
X
B
P
M
L
C
B
Dessiner un graphe représentant cette situation.
Est-il possible de trouver un trajet empruntant une fois et une seule toutes les rues de ce plan ? Justifier. Proposer un tel trajet
Est-il possible d’avoir un trajet partant et arrivant du même lieu et passant une fois et une seule par toutes les rues ?
Dimitri habite dans cette ville ; le graphe ci-dessous donne le nouveau plan du quartier avec les sens de circulation dans les différentes rues et le temps de parcours entre les différents lieux.
Dimitri désire prendre sa voiture pour se rendre de son domicile, noté D, jusqu’à la Piscine.
Proposer un trajet le plus court possible lui permettant de se rendre de son domicile à la Piscine.
La réponse devra être justifiée par un algorithme.