À l'occasion de la coupe du monde de football 2006 en Allemagne, une agence touristique organise des voyages en car à travers les différentes villes où se joueront les matchs d'une équipe nationale.
Les routes empruntées par les cars sont représentées par le graphe ci-dessous.
Le long de chaque arête figure la distance en kilomètres séparant les villes. Les lettres B, D, F, H, K, M, N et S représentent les villes Berlin, Dortmund, Francfort, Hambourg, Kaiserslautern, Munich, Nuremberg et Stuttgart.
En précisant la méthode utilisée, déterminer le plus court chemin possible pour aller de Kaiserslautern à Berlin en utilisant les cars de cette agence.
Pour déterminer le plus court chemin possible pour aller de Kaiserslautern à Berlin on utilise l'algorithme de Dijkstra.
Pour des raisons de sécurité, les supporters de certaines équipes nationales participant à la coupe du monde de football en 2006 ne peuvent être logés dans le même hôtel.
On donne ci-dessous le graphe d'incompatibilité entre les supporters de différentes équipes : par exemple, un supporter de l'équipe A ne peut être logé avec un supporter de l'équipe P.
Déterminer le nombre chromatique de ce graphe en justifiant la valeur trouvée.
Proposer une répartition des supporters par hôtel en utilisant un nombre minimum d'hôtels.
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.