Sarah, une jeune étudiante en géologie, souhaite partir en voyage en Islande avec des amis. Elle a loué une voiture tout terrain pour pouvoir visiter les lieux remarquables qu'elle a sélectionnés.
Sarah a construit le graphe ci-dessous dont les sommets représentent les lieux à visiter et les arêtes représentent les routes ou pistes :
| B : Le lagon bleu. | H : Rocher Hvítserkur. | M : Lac de Mývatn. |
| D : Chute d'eau de Dettifoss. | J : Lagune glacière de Jökulsárlón. | R : Capitale Reykjavik. |
| G : Geyser de Geysir. | L : Massif du Landmannalaugar. | V : Ville de Vík. |
Dans cette question, chaque réponse sera justifiée.
Déterminer l'ordre du graphe.
Il y a 9 sommets donc le graphe est d'ordre 9.
Déterminer si le graphe est connexe.
La chaîne H - R - B - V - G - L - J - M - D 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.
Déterminer si le graphe est complet.
Les sommets D et J ne sont pas adjacents donc le graphe n'est pas complet.
Sarah désire emprunter toutes les routes une et une seule fois. Déterminer, en justifiant, si cela est possible.
Emprunter toutes les routes une et une seule fois c'est chercher une chaîne eulérienne. Déterminons le degré de chacun des sommets :
| Sommets | B | D | G | H | J | L | M | R | V |
| Degré | 2 | 1 | 3 | 2 | 3 | 4 | 5 | 3 | 5 |
Il y a six sommets de degré impair donc le graphe n'admet pas une chaîne eulérienne. Par conséquent, il n'existe pas de circuit qui permette à Sarah d'emprunter toutes les routes une et une seule fois.
On appelle M la matrice associée au graphe précédent sachant que les sommets sont placés dans l'ordre alphabétique. On donne ci-dessous une partie de la matrice M ainsi que la matrice :
Il manque certains coefficients de la matrice M. Compléter et recopier uniquement la partie manquante de cette matrice.
Les coefficients de la partie manquante de la matrice d'adjacence M sont : .
Donner, en le justifiant, le nombre de chemins de longueur 4 permettant d'aller de B à D.
Le terme situé à l'intersection de la première ligne et de la deuxième colonne de la matrice est égal à 3 par conséquent, il y a trois chemins de longueur 4 permettant d'aller de B à D.
Sur le graphe pondéré ci-dessous, on a indiqué sur les arêtes les distances en kilomètre entre les différents lieux .
Déterminer à l'aide de l'algorithme de Dijkstra la distance minimale permettant d'aller du sommet B (Lagon bleu) au sommet D (Chute d'eau de Dettifoss).
Préciser alors le trajet à emprunter.
| B | D | G | H | J | L | M | R | V | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | B (0) |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 50 (B) | 220 (B) | R (50) | |
| ∞ | 150 (R) | 272 (R) | ∞ | ∞ | ∞ | 220 (B) | G (150) | ||
| ∞ | 272 (R) | ∞ | 291 (G) | ∞ | 220 (B) | V (220) | |||
| ∞ | 272 (R) | 412 ( V) | 291 (G) | 670 (V) | H (272) | ||||
| ∞ | 412 ( V) | 291 (G) | 567 (H) | L (291) | |||||
| ∞ | 412 ( V) | 567 (H) | J (412) | ||||||
| ∞ | 567 (H) | M (567) | |||||||
| 617 (M) | D (617) |
Le sommet D étant marqué, pour lire la chaîne de poids minimal, on part de D et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet le plus court permettant d'aller du sommet B (Lagon bleu) au sommet D (Chute d'eau de Dettifoss) est B - R - H - M - D. La distance parcourue est de 617 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.