Le graphe orienté ci-dessous modélise le plan de circulation des poids lourds entre différents villages d'une zone touristique. Les arêtes sont pondérées par les distances entre deux villages, exprimées en kilomètres.
Un fournisseur dont le dépôt est situé dans le village D doit effectuer une livraison de produits frais, en camion frigorifique, à un client du village B.
À l'aide d'un algorithme, déterminer l'itinéraire le plus court entre les villages D et B. Quelle est la distance parcourue ?
Pour déterminer le trajet le plus rapide pour aller de D à B, on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | G | H | Sommet sélectionné |
| ∞ | ∞ | ∞ | 0 | ∞ | ∞ | ∞ | ∞ | D (0) |
| ∞ | ∞ | 15 (D) | 9 (D) | ∞ | ∞ | ∞ | E (9) | |
| ∞ | ∞ | 15 (D) | 16 (E) | ∞ | ∞ | C (15) | ||
| ∞ | 33 (C) | 16 (E) | ∞ | ∞ | F (16) | |||
| ∞ | 33 (C) | 24 (F) | 22 (F) | H (22) | ||||
| ∞ | 32 (H) | 24 (F) | G (24) | |||||
| ∞ | 32 (H) | B (32) |
Le sommet B étant marqué, pour lire la chaîne de poids minimal, on part de B et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet le plus court possible pour aller de A à G est D-E-F-H-B. La distance parcourue est de 32 km
Une agence de voyage propose un circuit touristique pour visiter les trois villages A, B et C. Le client peut choisir la durée du séjour dans chaque village.
L'agence distingue deux périodes, la haute et la basse saison, et différencie ses tarifs selon la période.
Les tarifs dans les différents villages, en euro par personne et par jour, sont donnés dans le tableau suivant.
| Village A | Village B | Village C | |
| Nombre de jours | 1 | 1 | 1 |
| Tarif haute saison | 160 | 220 | 140 |
| Tarif basse saison | 130 | 180 | 110 |
On note P la matrice .
Un client souhaite effectuer un circuit qui comprend quatre jours dans le village A, six jours dans le village B et deux jours dans le village C. On associe à ce choix la matrice .
Calculer le produit matriciel . Que représentent les termes de la matrice obtenue ?
. La durée du séjour est de 12 jours, pour un coût de 2240 € en haute saison et de 1820 € en basse saison.
Ce client dispose d'un budget de 2 000 euros. Pourra-t-il réaliser son voyage ?
Avec un budget de 2 000 euros, le client peut organiser son séjour en basse saison.
Dans le village C se trouve un camping dont le plan est schématisé par le graphe ci-dessous.
Les arêtes sont les allées du camping et les sommets les carrefours.
Afin d'optimiser le nettoyage des allées, le gestionnaire du camping souhaite établir un parcours qui passe une seule fois par chaque allée.
Un tel parcours est-il possible ?
Effectuer un parcours qui passe une seule fois par chaque allée c'est chercher si il existe une chaîne eulérienne.
La chaîne 1-2-3-4-5-6-7-8-9-10-11-12-13 contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets distincts, il existe au moins une chaîne de longueur inférieure ou égale à 12 ayant pour extrémités ces deux sommets. Le graphe est connexe.
Les degrés des sommets sont :
| Sommets | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| Degré | 4 | 2 | 4 | 2 | 4 | 2 | 2 | 4 | 2 | 4 | 4 | 4 | 2 |
Le graphe est connexe et tous les sommets sont de degré pair donc il existe un cycle eulérien.
Il existe un cycle eulérien donc il est possible d'effectuer un parcours qui passe une seule fois par chaque allée en partant de n'importe quel carrefour et en revenant à son point de départ.
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.