Scribd
Importer
249 vues1 page

TD4

Le document décrit deux exercices sur la recherche d'un arbre couvrant minimal dans un graphe. Le premier exercice demande de trouver l'arbre couvrant de valeur minimale pour un graphe donné en utilisant les algorithmes de Prim et Kruskal. Le deuxième exercice concerne l'installation d'un réseau de transmission de données entre une banque centrale et ses succursales au moindre coût.

Transféré par

Ouattara rebecca
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
249 vues1 page

TD4

Le document décrit deux exercices sur la recherche d'un arbre couvrant minimal dans un graphe. Le premier exercice demande de trouver l'arbre couvrant de valeur minimale pour un graphe donné en utilisant les algorithmes de Prim et Kruskal. Le deuxième exercice concerne l'installation d'un réseau de transmission de données entre une banque centrale et ses succursales au moindre coût.

Transféré par

Ouattara rebecca
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

 

                      

TD4 : Arbre couvrant minimal

Exercice1 : Trouver l'arbre couvrant de valeur minimale pour le graphe ci­dessous :

− Par l'algorithme de Prim
− Par l'algorithme de Kruskal

Exercice2 : 
Une banque désire installer au moindre coût un réseau de transmissions de données entre son 
agence centrale située dans le quartier de la Bourse à Paris et sept de ses succursales. Il s'agit d'un 
réseau arborescent composé de lignes privées point à point 2400 bauds avec des possibilités de 
concentrateurs. Le coût de constrution d'une ligne entre deux agences est donné par le tableau suivant 
(en unités monétaires) :

B O E R      S_laz L N C
Bourse             ­
Opéra 5 ­
Etoile 18 17 ­
République 9 11 27 ­
St­Lazare 13 17 23 20 ­
Louvre     7  12 15 1        15 ­
Neuilly 38 38 20 40 40 35 ­
Châtelet 22 15 25 25 30 10 45 ­

. Quel problème reconnaissez vous ?
. Déterminer la solution optimale au problème.

Vous aimerez peut-être aussi