L'organisatrice d'une course à pied dans la ville de Berlin voudrait faire passer les participants par les lieux suivants :
On peut résumer la situation par le graphe ci-dessous :
Les lieux sont représentés par les sommets, et les rues ouvertes à la course par les arêtes.
Quel est l'ordre de ce graphe ?
Il y a six sommets donc le graphe est d'ordre 6.
Est-il complet ? Justifier.
Les sommets A et R ne sont pas ajacents donc le graphe n'est pas complet.
Est-il connexe ? Justifier.
La chaîne fermée A - P - C - F - R - B - A contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets du graphe il existe au moins une chaîne les reliant donc le graphe est connexe.
L'organisatrice peut-elle envisager un parcours passant par tous ces lieux en empruntant une seule fois chacune des rues ? Justifier.
Les degrés des sommets sont :
| Sommets | A | B | C | F | P | R |
| Degré | 4 | 5 | 4 | 4 | 3 | 2 |
Le graphe est connexe et il n'y a que deux sommets B et P de degré impair, il existe donc des chaînes eulérienne d'extrémités B et P.
L'organisatrice peut envisager un parcours passant par tous ces lieux en empruntant une seule fois chacune des rues.
Par exemple le trajet B - R - F - B - C - P - A - C - F - A - B - P.
Peut-elle envisager un parcours passant par tous ces lieux en empruntant une seule fois chacune des rues, et dont le départ et l'arrivée se font au même endroit ?
Il y a deux sommets de degré impair, il n'existe pas de cycle eulérien.
L'organisatrice ne peut pas envisager un parcours passant par tous ces lieux en empruntant une seule fois chacune des rues, et dont le départ et l'arrivée se font au même endroit.
Donner la matrice d'adjacence M de ce graphe, en rangeant les sommets dans l'ordre alphabétique.
La matrice d'adjacence du graphe est
On admet que : . Combien de parcours peut-on envisager d'Alexanderplatz au Reichstag passant par exactement 3 rues ?
Justifier la réponse.
Le coefficient de la première ligne et sixième colonne de la matrice est égal au nombre de chemins permettant de se rendre d'Alexanderplatz au Reichstag passant par exactement 3 rues.
donc il y a cinq trajets permettant de se rendre d'Alexanderplatz au Reichstag passant par exactement 3 rues.
(Les cinq trajets sont : A – B – F – R ; A – C – F – R ; A – C – B – R ; A – F – B – R et A – P – B – R.)
L'organisatrice veut également prévoir un autre parcours pour les coureurs moins expérimentés. Ce parcours doit débuter à Alexanderplatz et se terminer au Reichstag.
Les distances entre les différents lieux sont indiquées en kilomètres sur le graphe ci-dessous.
Déterminer le parcours le plus court possible d'Alexanderplatz au Reichstag. Donner sa longueur.
À l'aide de l'algorithme de Dijkstra, déterminons le parcours le plus court possible d'Alexanderplatz au Reichstag :
| A | B | C | F | P | R | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 6 (A) | 5 (A) | 3,5 (A) | 2 (A) | ∞ | P (2) | |
| 6 (A) | 4 (P) | 3,5 (A) | ∞ | F (3,5) | ||
| 6 (A) | 4 (P) | 8,5 (F) | C (4) | |||
5,5 (C) | 8,5 (F) | B (5,5) | ||||
6 (B) | R (6) |
Le sommet R étant marqué, pour lire la chaîne de poids minimal, on part de R et on remonte la chaîne en suivant les prédécesseurs. .
Le parcours le plus court possible d'Alexanderplatz au Reichstag est A - P - C - B - R, la distance parcourue est de 6 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.