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

> 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’ordre alphabétique). (0,75 point)

> 2. a)  Donner la matrice  associée au graphe (les sommets seront mis dans l’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)

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

> 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’il a un rendez-vous avec le responsable de l’hôpital situé en zone G.

a) En utilisant l’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)