À 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.
| K | F | H | S | M | N | D | B | Sommet sélectionné et commentaires |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | K de poids 0 et on marque le sommet adjacent F |
| 120 (K) | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | F on marque le sommet adjacent H de poids 610 =120+490 | |
| 610 (F) | ∞ | ∞ | ∞ | ∞ | ∞ | H on marque les sommets adjacents S, M et N | ||
| 1260 (H) | 1390 (H) | 1210 (H) | ∞ | ∞ | N (1210+210>1260 on conserve le poids de S ) | |||
| 1260 (H) | 1390 (H) | ∞ | ∞ | S on marque B (1260+230>1390 on conserve le poids de M ) | ||||
| 1390 (H) | ∞ | 1890 (S) | M on marque D (1390+580>1890 on conserve le poids de B ) | |||||
| 1990 (M) | 1890 (S) | B | ||||||
| 1990 (M) | D |
Le plus court chemin pour arriver en B arrive de S qui arrive de H en arrivant de F qui arrive de K.
Le plus court chemin possible pour aller de Kaiserslautern à Berlin est : Kaiserslautern-Francfort-Hambourg-Stuttgart-Berlin avec une distance parcourue de 1890 km.
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.
Notons γ le nombre chromatique du graphe.
Donc .
Effectuons un coloriage du graphe à l'aide de l'algorithme "glouton" :
Avec l'algorithme "glouton", une coloration du graphe à l'aide du nombre minimal de 4 couleurs est possible :
Le nombre chromatique du graphe est 4.
Proposer une répartition des supporters par hôtel en utilisant un nombre minimum d'hôtels.
Quatre hôtels sont nécessaires : un hôtel pour les supporters des équipes A, et R; un hôtel pour les supporters des équipes E, C et G , un troisième hôtel pour les supporters de l'équipe P et un quatrième hôtel pour les supporters de l'équipe Q.
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.