{"id":130,"date":"2009-07-15T14:49:16","date_gmt":"2009-07-15T12:49:16","guid":{"rendered":"http:\/\/wp1.fredptitgars.net\/index.php\/2009\/07\/15\/les-flots\/"},"modified":"2009-07-15T14:49:16","modified_gmt":"2009-07-15T12:49:16","slug":"les-flots","status":"publish","type":"post","link":"https:\/\/fredptitgars.ovh\/?p=130","title":{"rendered":"Les flots"},"content":{"rendered":"

Calcul du flot maximum dans un graph reliant le puits (t) \u00e0 la source(s).
\n
Il faut respecter la loi de kirshoff: l’ensemble flux entrant sur un n\u0153ud=l’ensemble des flux sortant du m\u00eame n\u0153ud<\/p>\n

Algorithme de Ford -Fulkerson<\/h2>\n

Recherche du flot complet<\/p>\n

    \n
      \n
    1. On fait passer un flot au juger<\/li>\n
    2. Am\u00e9liorer le flot jusqu’\u00e0 ce qu\u2019on ait un flot complet- Flot qui sature suffisamment de relations pour que tout chemin entre source, s et la sortie t comporte au moins un arc satur\u00e9.<\/li>\n<\/ol>\n
    3. Proc\u00e9dure de marquage\n
        \n
      1. Marquer l \u2019entr\u00e9e du r\u00e9seau (+)<\/li>\n
      2. Marquer toute extr\u00e9mit\u00e9, j, d \u2019un arc (i,j) non satur\u00e9 si origine,i , est marqu\u00e9e (+)<\/li>\n
      3. Marquer l \u2019origine, k, (-) d \u2019un arc (k, l) transportant un flot non nul si extr\u00e9mit\u00e9,l , est marqu\u00e9e<\/li>\n
      4. Si on ne peut marquer l \u2019extr\u00e9mit\u00e9, t, sortie du graphe, le flot est maximum<\/li>\n
      5. Sinon le flot n \u2019est pas maximum. Am\u00e9liorer le flot en respectant les lois de Kirchoff. Retour en 3-1<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n

        Dans cette exemple les valeur entre parenth\u00e8se repr\u00e9sente la valeur maximal, \u00e0 cot\u00e9 la valeur que l’on fait pass\u00e9.<\/p>\n

        Etape 1:<\/strong>
        \nOn fait pass\u00e9 un flot au jug\u00e9 de pour obtenir sur tous chemin au moins un arc satur\u00e9.:
        \n
        SA: 15, SB: 35, SC: 30, AD: 5 , AF: 15, etc…
        \n
        toujours en respectant la loi de kirshoff<\/p>\n

        \"r\u00e9seau
        r\u00e9seau de transport R=(X,U,C)<\/strong><\/figcaption><\/figure>\n

        V\u00e9rification:
        \nen partant de S, je peux aller vers A en prenant un arc non satur\u00e9 puis la seule solution est d’aller vers D car AF est satur\u00e9 et de D je suis coinc\u00e9 car plus de solution non satur\u00e9e SB est d\u00e9j\u00e0 satur\u00e9, donc fini. Enfin je peux prendre l’arc SC de C, je ne peux aller que vers E et la, je suis coinc\u00e9, donc c’est Ok.<\/p>\n

        \u00c9tape 2 Marquage:<\/strong><\/p>\n

        \"graph2-5.png\"<\/p>\n

        On part de la source S que l’on marque d’un +, puis on va regarder chaque arc partant d’un ‘+’ ,
        \n
        si l’arc n’est pas satur\u00e9, alors l’extr\u00e9mit\u00e9 est aussi marqu\u00e9e d’un ‘+’ SC n’est pas satur\u00e9, donc je marque le point C d’un signe ‘+’. je pouvais \u00e9galement marquer A d’un + si l’arc est satur\u00e9, je le marque d’un signe ‘-‘ , donc, je marque B d’un ‘-‘ car SB est satur\u00e9.
        \n
        Je part de C, ou je peut all\u00e9 \u00e0 E ou F. F est satur\u00e9, on peut le marqu\u00e9 de ‘-‘, mais pas int\u00e9ressant, E n’est pas satur\u00e9, on le marque de ‘+’. Depuis E, je ne peux pas aller direct a l’arriv\u00e9e car c’est satur\u00e9, mon objectif est d’arriver a la fin T.
        \n
        Par contre, je peux reculer vers B car il est marqu\u00e9 de ‘-‘ et de B, je peux aller vers F car l’arc n’est pas satur\u00e9, donc je peux marque F d’un ‘+’. Enfin, de F, je peux rejoindre le puits T car FT n’est pas satur\u00e9. J’ai donc identifi\u00e9 un chemin que je peux optimiser le chemin est le suivant : SCEBFT<\/em> <\/p>\n

        \"graph3-4.png\"<\/p>\n

        On regarde la capacit\u00e9 d’optimisation sur chaque arc, quand on avance : les noeuds marqu\u00e9s d’un +
        \n
        La marge est la diff\u00e9rence entre ce qui passe r\u00e9ellement et la capacit\u00e9. Vous avez sur SC, vous avez une capacit\u00e9 de 40 mais seulement 30 passent, donc vous avez une marge de 10.
        \n
        Quand vous allez vers un n\u0153ud marqu\u00e9 ‘-‘, vous avez une capacit\u00e9 de revenir \u00e0 zero, donc la marge est entre 0 et ce qui passe r\u00e9ellement. Sur la chaine \u00e0 am\u00e9liorer, le minimum est de 5 entre B et F, donc on va ajouter 5 \u00e0 chaque chemin + et retirer 5 \u00e0 chaque chemin marqu\u00e9 – les nouvelles valeurs sont sur le second graphe ci dessus<\/p>\n

        \"graph4-3.png\"<\/p>\n

          \n
        1. Flot am\u00e9lior\u00e9<\/li>\n
        2. Marquage sorite: impossible
          \n=> flot maximal=85<\/li>\n<\/ol>\n

          Sommet marqu\u00e9s 1= S,A,B,C,D,E<\/em>
          \n
          Sommet non marqu\u00e9s: A*=T,F<\/em><\/p>\n

          \nCapacit\u00e9 de la coupe C s\u00e9parant les sommets marqu\u00e9s des sommets non marqu\u00e9s $\\omega^+$=20+30+10+5+20=85\n<\/math>
          \nLe flot est optimal quelle est sa valeur ?
          \n
          La somme de tous les flux qui arrivent en T
          \n
          soit : 20 + 30 + 35 =85 qui correspond au flot maximal
          \nAu lieu d’optimiser en partant de C, nous aurions pu le faire en passant par A
          \nSADBFT est aussi un chemin qui permet d’optimiser on aurait pu l’am\u00e9liorer seulement de 5 aussi.<\/p>\n","protected":false},"excerpt":{"rendered":"

          Calcul du flot maximum dans un graph reliant le puits (t) \u00e0 la source(s). Il faut respecter la loi de kirshoff: l’ensemble flux entrant sur un n\u0153ud=l’ensemble des flux sortant du m\u00eame n\u0153ud Algorithme de Ford -Fulkerson Recherche du flot complet On fait passer un flot au juger Am\u00e9liorer le flot jusqu’\u00e0 ce qu\u2019on ait […]<\/p>\n","protected":false},"author":2,"featured_media":126,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-130","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-rcp101-recherche-operationnelle-et-aide-a-la-decision"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/130","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=130"}],"version-history":[{"count":0,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/130\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/media\/126"}],"wp:attachment":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}