Dans le graphe ci-dessous, les sommets représentent différentes zones de résidence ou d&rsquo activités d&rsquo une municipalité. Une arête reliant deux de ces sommets indique l&rsquo existence d&rsquo une voie d&rsquo accès principale entre deux lieux correspondants.

&gt  1. Donner, sans justifier, le degré de chacun des sommets (la réponse pourra être présentée sous forme de tableau où les sommets seront mis dans l&rsquo ordre alphabétique). (0,75 point)

&gt  2. a)  Donner la matrice  associée au graphe (les sommets seront mis dans l&rsquo ordre alphabétique). (0,5 point)

b) On donne la matrice .

Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant et , puis donner leur liste. (1 point)

&gt  3. Pour sa campagne électorale, un candidat souhaite parcourir toutes les voies d&rsquo accès principales de ce quartier sans emprunter plusieurs fois la même voie. Montrer qu&rsquo un tel parcours est possible. (0,75 point)

&gt  4. Dans le graphe ci-dessous, les valeurs indiquent, en minutes, les durées moyennes des trajets entre les différents lieux via les transports en commun.

Ce même candidat se trouve à la mairie () quand on lui rappelle qu&rsquo il a un rendez-vous avec le responsable de l&rsquo hôpital situé en zone G.

a) En utilisant l&rsquo algorithme de Dijkstra, déterminer le chemin de durée minimale que ce candidat devra emprunter pour arriver à son rendez-vous. (1,5 point)

b) Combien de temps faut-il prévoir pour effectuer ce trajet ? (0,5 point)