Un guide fait visiter six sites touristiques notés B, C, D, E, F et G.
Les tronçons de route qu’il peut emprunter sont représentés sur le graphe ci-dessous.
Le long de chaque arête figure la distance en kilomètres des différents tronçons.
2. Ce graphe est-il complet? Connexe?
3. a) A partir de l’hôtel, le guide peut-il emprunter tous les tronçons de route en passant une et une seule fois sur chacun d’eux ? Justifier la réponse.
b) Même question s’il doit obligatoirement terminer son circuit à l’hôtel.
4. a) Encadrer le nombre chromatique
b) Colorier le graphe et déduire le nombre chromatique
5. Déterminer le plus court chemin menant de l’hôtel A au site E. Justifier la réponse par un algorithme. Quelle est la longueur de ce chemin ?
0 commentaires:
Enregistrer un commentaire