Un orchestre doit effectuer une tournée passant par les villes A, B, C, D, E, F, G et H, en utilisant le réseau autoroutier.
Le graphe Γ ci-dessous représente les différentes villes de la tournée et les autoroutes reliant ces villes (une ville est représentée par un point, une autoroute par une arête) :
Est-il possible d'organiser la tournée en passant au moins une fois par chaque ville, tout en empruntant une fois et une seule chaque tronçon d'autoroute ? (la réponse sera justifiée). Si oui citer un trajet de ce type.
Organiser la tournée en passant au moins une fois par chaque ville, tout en empruntant une fois et une seule chaque tronçon d'autoroute c'est chercher si le graphe contient une chaîne eulérienne.
La chaîne A-B-D-F-H-G-E-C contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe est connexe.
Dans un graphe non orienté, le degré d'un sommet du graphe est le nombre d'arêtes issues de ce sommet. D'où :
| Sommets | A | B | C | D | E | F | G | H |
| Degré des sommets du graphe | 2 | 3 | 4 | 4 | 3 | 2 | 2 | 4 |
Ainsi, le graphe Γ est connexe et contient seulement deux sommets de degré impair donc il existe une chaîne eulérienne commençant par un des deux sommets de degré impair (B ou E) et finissant par le deuxième sommet de degré impair.
Il est possible d'organiser la tournée en passant au moins une fois par chaque ville, tout en empruntant une fois et une seule chaque tronçon d'autoroute par exemple B-D-F-H-E-G-H-D-C-A-B-C-E.
On appelle M la matrice associée au graphe Γ (les sommets étant pris dans l'ordre alphabétique).
On donne la matrice : Combien existe-t-il de chemins de longueur 3 reliant B à H? (la réponse devra être justifiée). Préciser ces chemins.
Les sommets de la matrice M sont pris dans l'ordre alphabétique, par conséquent, le terme situé à l'intersection de la deuxième ligne et de la huitième colonne de la matrice , donne le nombre de chaînes de longueur 3 partant du sommet B et aboutissant au sommet H.
Il y a 3 chaînes de longueur 3 partant du sommet B et aboutissant au sommet H : B-C-D-H, B-C-E-H et B-D-F-H.
Des contraintes de calendrier imposent en fait d'organiser un concert dans la ville F immédiatement après un concert dans la ville A.
Le graphe Γ est complété ci-dessous par les longueurs en kilomètres de chaque tronçon (les longueurs des segments ne sont pas proportionnelles aux distances).
Déterminer, en utilisant un algorithme dont on citera le nom, le trajet autoroutier le plus court (en kilomètres) pour aller de A à F. Préciser la longueur en kilomètres de ce trajet.
Pour déterminer le trajet le plus court pour aller de A à F, on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | G | H | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 300 (A) | 500 (A) | ∞ | ∞ | ∞ | ∞ | ∞ | B (300) | |
| 500(A) | 700 (B) | ∞ | ∞ | ∞ | ∞ | C (500) | ||
| 600 (C) | 700 (C) | ∞ | ∞ | ∞ | D (600) | |||
| 700 (C) | 1300 (D) | ∞ | 1300 (D) | E (700) | ||||
| 1300 (D) | 900 (E) | 1000 (E) | G (900) | |||||
| 1300 (D) | 1000 (E) | H (1000) | ||||||
| 1200 (H) | F (1200) |
Le sommet F étant marqué, pour lire la chaîne de poids minimal, on part de F et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet le plus court possible pour aller de A à F est A-C-E-H-F. La distance parcourue est de 1200 km.
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.