Les parties I et II sont indépendantes
Le graphe Γ suivant représente le plan d'un zoo.
Le sommet A représente son accès. Les sommets B, C, D, E, F et G désignent les différents secteurs animaliers de ce zoo.
Une arête représente l'allée reliant deux secteurs et est pondérée par la distance de parcours, exprimée en mètres, entre ces deux secteurs.
AB = 90, AC = 290, AD = 175, AE = 150, BC = 185, BD = 155, BE = 180, CD = 120, CG =260, DE = 110, DF = 105, EF = 135, FG = 230.
Pour mieux visualiser sur le plan les différents secteurs du zoo, on veut les colorier de telle sorte que deux secteurs adjacents ne soient pas de la même couleur.
Quel est le nombre minimum de couleurs nécessaires à la réalisation de ce plan ? Justifier la réponse,
Donner un encadrement du nombre chromatique du graphe Γ . Justifier la réponse.
Proposer alors une telle coloration.
Pour nettoyer les allées, les services techniques du zoo utilisent une balayeuse automobile.
Est-il possible que cette balayeuse n'emprunte chaque allée qu'une fois et une seule ? Si oui, proposer un tel chemin, sinon justifier votre réponse.
Emprunter chaque allée une fois et une seule c'est chercher si le graphe contient une chaîne eulérienne.
Les services de sécurité basés au point A doivent intervenir dans le secteur G. Déterminer, à l'aide d'un algorithme, l'itinéraire le plus court.
Pour déterminer l'itinéraire le plus court pour aller de A à G, utiliser l'algorithme de Dijkstra.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.