Scribd Logo
Importer

Bienvenue sur Scribd !

  • 113 vues

    Méthode de FORD-Fulkerson

    Transféré par

    ahmed fahssi

    Droits d'auteur :

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

    Méthode de FORD-Fulkerson

    Transféré par

    ahmed fahssi
    113 vues33 pages

    Titre original

    Méthode_de_FORD-Fulkerson.pptx

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PPTX, PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PPTX, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pptx, pdf ou txt
    113 vues33 pages

    Méthode de FORD-Fulkerson

    Transféré par

    ahmed fahssi

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PPTX, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pptx, pdf ou txt
    sur 33

    Demandé par : Akef Fatiha

    Filière : MLI-1

    Flot maximal dans un réseau de transport


    (méthode de Ford-Fulkerson)
    Realisé par:
    El-Amoumri Ayoub
    Demandé par :
    Krafess Omar
    Akef Fatiha Raziq ayoub
    EL MouaLlif Wissal
    Chadli Abdelhaq

    11/19/2020
    PLAN:
    INTRODUCTION
    I. Rappels et Définitions
    II. Flot dans un graphe
    III. PROBLÈME DE FLOT
    IV. Algorithme de Ford-Fulkerson
    V. Exercices

    11/19/2020 2
    I. Rappels et Définitions :

    11/19/2020 3
    1. Graphe

    11/19/2020 4
    11/19/2020 5
    11/19/2020 6
    2. Graphe valué :

    11/19/2020 7
    3. Représentation d’un graphe

    11/19/2020 8
    11/19/2020 9
    II. Flot dans un graphe

    11/19/2020 10
     Le problème du flot maximal est l’un des problèmes des réseaux de transport.
     Un réseau est un graphe orienté, G = (E, Γ, c).

    Exemple :
     Problèmes de circulation d’objets (voiture, information ...) dans un réseau
    (routier, informatique ...).
    Définition :
    Soit G = (E, Γ, c), un graphe valué comportant un seul sommet source s et un
    seul sommet puits t.
    •Un flot de s à t est une fonction f : Γ →R tq

    11/19/2020 11
    Exemple :

    11/19/2020 12
    •Pour tout sommet j ≠ s, t. On dit qu’il y a conservation du flux au
    sommet j ("ce qui rentre égale ce qui sort").

    • Le flot est dit réalisable si pour toute arête (i, j) ∈ Γ, on a


    0≤ fij ≤ cij

    • Un arc (i,j) est dit saturé pour un flot f si f (i,j) = c(i,j). 

    11/19/2020 13
    III-PROBLÈME DE FLOTS

    11/19/2020 14
    1. Les réseaux de transport
    Réseau de transport :
    graphe orienté avec pour chaque arc une capacité.
    La capacité c(u, v) est un entier positif ou nul.
    Il y a aussi une source s et un puits t.
    Aucun arc n'arrive à la source et aucun arc ne quitte le puits.
    Un flot est une fonction entière positive ou nulle f définie sur les arcs satisfaisant :
     
     Contrainte de capacité : f(u, v) ≤ c(u, v)
     Symétrie : f(u, v) = – f(v, u)
     Conservation du flot : pour tout sommet autre que s et t, la somme des flots
    sur les arcs entrants et la somme des flots sur les arcs sortants sont égales ("Loi de
    Kirchhoff").

    Exemples : circuits électriques ou hydrauliques, réseaux de communication,


    modélisation de transports
    11/19/2020 15
    Rq: Quand deux arcs en sens inverse relient deux sommets, on peut toujours
    annuler la fonction flot sur l'un des deux.
    11/19/2020 16
    1. flot maximum
    • chaine d’un graphe

    11/19/2020 17
    • chemin améliorant

    11/19/2020 18
    • le réseau résiduel
    Il existe toujours un flot possible qui est le flot nul.
    Problème : comment trouver un flot qui a la valeur maximum ?
    Celui de l'exemple est-il maximum ?
     
    Recherche d'un chemin améliorant.

    Déterminer le réseau résiduel :


     
    pour chaque arc (u, v), f(u, v) ≤ c(u, v), on peut augmenter le flot de c(u, v) − f(u, v), et
    on peut le diminuer de f(u, v), donc faire passer un flot f(u, v) sur l'arc (v, u).
    Si cet arc existe déjà avec une capacité c(v, u), celle-ci s'ajoute à f(v, u).
     
    Le graphe orienté avec ces capacités est le réseau résiduel.
     
    On cherche un chemin de s à t dans le réseau résiduel. Il correspond à une possibilité
    d'amélioration du flot en modifiant de la valeur du minimum des capacités résiduelles
    sur le chemin.
     
    11/19/2020 19
    • amélioration d’un flot

    « Ɛ » représente l’amélioration qu’on peut apporter au flot.

    11/19/2020 20
    • Exemple

    11/19/2020 21
    IV. Algorithme de Ford-Fulkerson

    11/19/2020 22
    BUT :
    L’algorithme de Ford-Fulkerson permet de trouver un flot maximal par
    recherche de chaînes améliorantes. Il est basé sur le résultat suivant :

    11/19/2020 23
    11/19/2020 24
    11/19/2020 25
    Le théorème de Ford-Fulkerson permet de savoir si un flot est maximal ou non.
    Par exemple :

    11/19/2020 26
    11/19/2020 27
    11/19/2020 28
    Construction d’une coupe minimale ( )

    11/19/2020 29
    11/19/2020 30
    11/19/2020 31
    11/19/2020 32
    V. Exercices :

    11/19/2020 33

    Vous aimerez peut-être aussi