TD2 TG [PDF]

Zitiervorschau

Théorie des graphes

TD2 Plus court chemin (pcc)

2020-2021 1 G. Indus A et B

A- ALGORITHME DIJKSTRA Exercice 1 Le réseau informatique d’une entreprise est représenté par le graphe qui suit. Les sommets représentent les serveurs et les arêtes indiquent le temps nécessaire pour faire passer une information d’un ordinateur à l’autre. 1. Un employé travaillant sur l’ordinateur A envoie un document à un collègue utilisant l’ordinateur K. Combien de temps faudra-t-il au minimum pour que le document lui parvienne ? 2. Le serveur F tombe en panne à cause d’un virus. Combien de temps faut-il maintenant pour envoyer un document de A à K ?

Exercice 2 Un routier veut aller de la ville D à la ville I en empruntant le réseau déterminé par les villes A, B, C, D, E, F, G, H et I. Ce réseau est modélisé par le graphe orienté suivant :

1. On appliquera l’algorithme de DIJKSTRA pour résoudre le problème (on indiquera le tableau obtenu): le routier doit se rendre de la ville D à la ville I, on veut savoir par quelles villes il doit passer pour parcourir le moins de kilomètres possibles, sachant que la valuation d’un arc (i,j) représente la distance en kilomètre entre les villes i et j . 2. Si on désire se rendre de D à F ? Donner alors la solution. 1

B- ALGORITHME DE BELLMAN-FORD Exercice 3 Trouver le pcc entre a et h, par application de l’algorithme de Bellman-Ford au graphe suivant :

Exercice 4 Les sept pays, les Pays-Bas, la Belgique, l’Allemagne, la Suisse, l’Italie, l’Espagne et la France, produisent, exportent, importent et consomment le beurre. Certains de ces pays surproduisent et sont obligé d’exporter, d’autres doivent importer. Le gouvernement de chaque pays décide de créer un organisme dont le rôle est d’aider les échanges. Pour cela, dans un premier temps, chaque pays passe un accord commercial avec chacun de ses voisins fixant des aides pour l’exportation vers des pays déficitaires et des taxes pour l’exportation vers des pays surproducteurs. Les données sont résumées dans le tableau 1. Les nombres dans chaque case du tableau représentent les taxes, les aides et les coûts de transport sous forme taxe/aide/coût Indication: Les dépenses pour acheminer le beurre d’un pays à un autre se calcule par la formule : taxe − aide + coût.

PB PB B A S I F E

15/0/2 5/0/4

B 0/15/2

A 0/5/4 8/0/3

0/10/3

S

5/0/3 0/5/3

0/10/2

I

0/15/4

0/15/2 15/0/2 0/5/5

F

E

22/0/2 15/0/4 5/0/5 8/0/6

0/8/6

0/5/6 5/0/6

1. Modéliser le problème sous forme d’un problème de plus court chemin dans un graphe orienté valué. Que remarque-t-on ? 2. La commission européenne propose de réduire de 15 à 10 l’aide à l’exportation de la France vers l’Allemagne. Quelle en est la raison ? 3. Résoudre le problème de l’exportation du beurre des Pays-Bas vers l’Espagne. 2