Un restaurateur se fournit auprès de 5 producteurs locaux. Le graphe ci-dessous représente la situation géographique du restaurateur et de ses fournisseurs, les arêtes correspondant au réseau routier et les sommets aux producteurs :
Légende E : éleveur |
Le graphe est-il complet ? Justifier la réponse.
Le graphe est d'ordre 6 et tous les sommets ne sont pas de degré 5 donc le graphe n'est pas complet.
Le graphe est-il connexe ? Justifier la réponse.
Le cycle R - P - E - M - F - V - R contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets, il existe une chaîne les reliant. Donc le graphe est connexe.
Est-il possible pour le restaurateur d'organiser une visite de tous ses producteurs en partant de son restaurant et en empruntant une fois et une seule chaque route ? Justifier la réponse. Si oui, préciser le point d'arrivée et proposer un tel parcours.
Le graphe est connexe et il n'y a que deux sommets de degré impair R et V par conséquent, il existe des chaînes eulériennes d'extrémités R et V.
Le restaurateur peut organiser une visite de tous ses producteurs en partant de son restaurant et en empruntant une fois et une seule chaque route en terminant par le vigneron.
Un parcors possible est : R - P - E - M - F - E - R - V - P - F - V.
On appelle N la matrice d'adjacence associée à ce graphe, les sommets étant pris dans l'ordre alphabétique.
Déterminer la matrice N.
La matrice d'adjacence associée à ce graphe, les sommets étant pris dans l'ordre alphabétique est : .
On donne la matrice .
Déterminer, en justifiant la réponse, le nombre de chemins de longueur 3 reliant l'éleveur au vigneron.
Le coefficient de la matrice situé à l'intersection de la cinquième ligne et de la sixième colonne est égal à 8. Il y a huit chaînes de longueur 3 reliant l'éleveur au vigneron.
Les arêtes du graphe sont pondérées par les distances, exprimées en kilomètre, entre les différents lieux :
Le restaurateur doit se rendre chez le maraîcher en partant de chez lui. Quel est le plus court chemin pour effectuer ce trajet ? Justifier la réponse à l'aide d'un algorithme.
Déterminons un parcours de distance minimale joignant le sommet R au sommet M à l'aide de l'algorithme de Dijkstra.
| R | E | F | P | V | M | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | R (0) |
| 5 (R) | ∞ | 4 (R) | 10 (R) | ∞ | P (4) | |
| 5 (R) | 11 (P) | 9 (P) | ∞ | E (5) | ||
| 11 (P) | 9 (P) | 13 (E) | V (9) | |||
10 (V) | 13 (E) | F (10) | ||||
12 (F) | M (12) |
Le sommet M étant marqué, pour lire la chaîne de poids minimal, on part de M et on "remonte" la chaîne en suivant les prédécesseurs : .
Le plus court chemin du restaurateur au maraîcher est de 12 kilomètres en effectuant le parcours R - P - V - F - M.
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.