On considère le graphe 𝒢 ci-dessous :
Déterminer en justifiant si ce graphe :
est connexe ;
La chaîne A-D-E-C-F-H-G-B 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.
admet une chaîne eulérienne.
Le graphe est connexe et tous ses sommets sont de degré pair alors, ce graphe amet un cyvle eulérien, donc une chaîne eulérienne.
On note M la matrice d'adjacence associée à ce graphe en prenant les sommets dans l'ordre alphabétique. On donne : Donner, en justifiant, le nombre de chemins de longueur 3 reliant E à B.
Les termes de la matrice donnent le nombre de chaînes de longueur 3 entre deux sommets du graphe.
Le terme de la matrice situé à l'intersection de la cinquième ligne et de la deuxième colonne est égal à 5.
Il existe cinq chemins de longueur 3 reliant E à B.
Un club alpin souhaite proposer à ses membres des randonnées de plusieurs jours dans les Alpes. À cet effet, huit refuges notés A, B, C, D, E, F, G et H ont été sélectionnés.
Le graphe 𝒢 de la partie A permet de visualiser les différents itinéraires possibles, les sommets représentant les refuges et les arêtes schématisant tous les sentiers de randonnée balisés les reliant.
D'après l'étude effectuée dans la partie A, le club alpin est-il en mesure de proposer :
un itinéraire au départ du refuge A qui passerait par tous les refuges en empruntant une fois et une seule fois chacun des sentiers ? Si oui, proposer un tel itinéraire ;
Le graphe admet un cycle eulérien donc il existe un itinéraire au départ du refuge A qui passe par tous les refuges en empruntant une fois et une seule fois chacun des sentiers. Par exemple l'itinéraire A-D-E-H-F-E-C-F-B-H-G-B-A.
des itinéraires de trois jours (un jour correspondant à une liaison entre deux refuges) reliant le refuge E au refuge B ? Si oui, combien peut-il en proposer ?
Il existe cinq chaînes de longueur 3 reliant E à B par conséquent, il existe cinq itinéraires de trois jours reliant le refuge E au refuge B.
Le graphe 𝒢 est complété ci-dessous par la longueur en kilomètres de chacun des sentiers.
Le club alpin désire aussi proposer à ses membres l'itinéraire le plus court reliant A à H.
Déterminer cet itinéraire et en préciser la longueur en kilomètres.
À l'aide de l'algorithme de Dijkstra, déterminons le trajet le plus court parcours pour se rendre de A à H
| A | B | C | D | E | F | G | H | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 12 (A) | ∞ | 14 (A) | ∞ | ∞ | ∞ | ∞ | B (12) | |
| ∞ | 14 (A) | ∞ | 21 (B) | 28 (B) | 33 (B) | D (14) | ||
| ∞ | 24 (D) | 21 (B) | 28 (B) | 33 (B) | F (21) | |||
| 31 (F) | 24 (D) | 28 (B) | 32 (F) | E (24) | ||||
| 31 (F) | 28 (B) | 32 (F) | G (28) | |||||
| 31 (F) | 32 (F) | C (31) | ||||||
| 32 (F) | H (32) |
Le sommet H étant marqué, pour lire la chaîne de poids minimal, on part de H et on "remonte" la chaîne en suivant les prédécesseurs. .
L'itinéraire le plus court reliant A à H est A - B - F - H. La distance parcourue est de 32 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.