Scribd
Importer
5 vues1 page

Exercice 1

Le document présente des exercices pratiques sur la théorie des graphes, incluant la détermination des plus courts chemins à partir d'un sommet donné, la construction d'un arbre de poids minimal, et l'analyse d'un réseau de transport avec un flot initial. Les exercices nécessitent l'application d'algorithmes connus pour résoudre des problèmes de graphes. Les résultats attendus incluent des tableaux de distances et des démonstrations de flots maximaux.

Transféré par

boublenzarayene999
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
5 vues1 page

Exercice 1

Le document présente des exercices pratiques sur la théorie des graphes, incluant la détermination des plus courts chemins à partir d'un sommet donné, la construction d'un arbre de poids minimal, et l'analyse d'un réseau de transport avec un flot initial. Les exercices nécessitent l'application d'algorithmes connus pour résoudre des problèmes de graphes. Les résultats attendus incluent des tableaux de distances et des démonstrations de flots maximaux.

Transféré par

boublenzarayene999
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

Université d’Oran 1 Ahmed Benbella- Faculté des Sciences Exactes et Appliquées

Département d’Informatique -Théorie des graphes -Travaux Dirigés No 3

Exercice 1
Soit le graphe suivant :

A partir d’un algorithme que vous connaissez, compléter le tableau suivant pour
déterminer les plus courts chemins du sommet E vers les autres sommets :

E A B C D F G S S
0 5 3 2     E
2 4 5 E,C

Exercice 2
Déterminer un arbre H de poids minimal recouvrant G par la méthode des tris

Exercice 3
Soit le réseau de transport suivant muni d’un flot initial 0 :

1-Compléter la répartition de 0 dans le réseau.


2-Prouver que 0 n’est pas maximal.
3-Détermner le flot maximal associé au réseau donné.

Vous aimerez peut-être aussi