Scribd Logo
Importer

Bienvenue sur Scribd !

  • 320 vues

    TD Flots

    Transféré par

    NoureddineLahouel
    Le document présente deux exercices sur le calcul de flot maximal dans des graphes. Le premier exercice demande de trouver un flot réalisable, de donner un intervalle pour tout flot possible et d'appliquer l'algorithme de Ford-Fulkerson. Le deuxième exercice demande de déterminer la valeur du flot maximal dans deux graphes donnés.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme DOC, PDF, TXT ou lisez en ligne sur Scribd

    TD Flots

    Transféré par

    NoureddineLahouel
    320 vues1 page
    Le document présente deux exercices sur le calcul de flot maximal dans des graphes. Le premier exercice demande de trouver un flot réalisable, de donner un intervalle pour tout flot possible et d'appliquer l'algorithme de Ford-Fulkerson. Le deuxième exercice demande de déterminer la valeur du flot maximal dans deux graphes donnés.

    Titre original

    TD flots

    Copyright

    © © All Rights Reserved

    Formats disponibles

    DOC, PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Le document présente deux exercices sur le calcul de flot maximal dans des graphes. Le premier exercice demande de trouver un flot réalisable, de donner un intervalle pour tout flot possible et d'appliquer l'algorithme de Ford-Fulkerson. Le deuxième exercice demande de déterminer la valeur du flot maximal dans deux graphes donnés.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme DOC, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format doc, pdf ou txt
    320 vues1 page

    TD Flots

    Transféré par

    NoureddineLahouel
    Le document présente deux exercices sur le calcul de flot maximal dans des graphes. Le premier exercice demande de trouver un flot réalisable, de donner un intervalle pour tout flot possible et d'appliquer l'algorithme de Ford-Fulkerson. Le deuxième exercice demande de déterminer la valeur du flot maximal dans deux graphes donnés.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme DOC, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format doc, pdf ou txt
    sur 1

    TD

    Flot dans les réseaux

    Exercice 1 :
    Soit le graphe G = (X, U) ci-dessous.
    1) Faire circuler un flot entre e et s. Quelle est la valeur du flot trouvé ?
    2) Sans chercher le flot maximum donner un intervalle dans lequel la valeur de tout flot
    réalisable doit se trouver. Justifier ce résultat.
    3) Appliquer l’algorithme de Ford-Fulkerson pour trouver le flot maximum. Débuter
    l’algorithme à partir d’un flot réalisable de valeur 5.

    Exercice 2 :
    Déterminer la valeur du flot maximal dans les graphes suivants :
     Graphe 1 :
     A B C D E F G H I
    A 6 7 6 5
    B 6 5 6 5
    C 3 4 7 6
    D 4 6 7 3
    E 5 6 3 5
    F 6 3 5
    G 6 2
    H 1

     Graphe 2 :
     a b c d E
    S 8
    a 5 6
    b 2 4 6
    c 9
    d 3

    Vous aimerez peut-être aussi