Pour aller plus loin : l'algorithme de Dijkstra pour calculer un nombre de chemins

1. a) Le graphe est simple car il y a au plus une arête entre deux sommets distincts et il n'y a pas de boucle.
   Un graphe complet est un graphe simple dont tous les sommets sont adjacents, c'est-à-dire que tout couple de sommets est relié par une arête.
   Le graphe proposé n'est pas complet car les sommets M et P ne sont pas adjacents.

2. b) Ce graphe est connexe car il existe une arête entre n'importe quelle paire de sommets distincts du graphe.

3. Montrons que ce graphe connexe admet une chaîne eulérienne.

Nous savons qu'un graphe connexe contient une chaîne eulérienne si et seulement si il possède 0 ou 2 sommets de degré impair.
Voici un tableau indiquant les degrés des sommets du graphe :

Comme il y a exactement deux sommets de degré impair (les sommets R et V), ce graphe connexe contient une chaîne eulérienne.
Par conséquent, il est 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.

Le parcours doit commencer ou se terminer par un sommet de degré impair, soit par R ou par V.
Puisque le restaurateur part de son restaurant, le point d'arrivée sera alors V.
Un parcours possible est : R - E - M - F - E - P - R - V - P - F - V.

3. a) La matrice d'adjacence associée au graphe orienté est
   $N=\begin{pmatrix}0&1&1&1&1&0\\1&0&1&1&0&1\\1&1&0&0&0&0\\1&1&0&0&1&1\\1&0&0&1&0&1\\0&1&0&1&1&0\end{pmatrix}$

4. b) L'énoncé donne
   $N^3=\begin{pmatrix}6&10&6&10&9&5\\10&6&6&10&5&9\\6&6&2&4&4&4\\10&10&4&8&8&8\\9&5&4&8&4&8\\5&9&4&8&8&4\end{pmatrix}$

Le coefficient $n_{1,6}$ de la matrice $N^3$ désigne le nombre de chemins de longueur 3 reliant l'éleveur au vigneron.
Puisque $n_{1,6} = 5$, il y a 5 chemins de longueur 3 reliant l'éleveur au vigneron.

4. Utilisons l'algorithme de Dijkstra afin de déterminer la distance minimale pour aller du restaurant au maraîcher.

D'où le chemin le plus court pour aller du restaurateur au maraîcher est R - P - V - F - M.
La longueur de ce trajet est de 12 km.