{"id":3587,"date":"2016-08-22T15:52:59","date_gmt":"2016-08-22T14:52:59","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=3587"},"modified":"2024-02-11T20:01:09","modified_gmt":"2024-02-11T19:01:09","slug":"probleme-de-flot-maximum","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/","title":{"rendered":"Maximum flow problem 101"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"3587\" class=\"elementor elementor-3587\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-311cf1d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"311cf1d\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-6002512\" data-id=\"6002512\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-55dcec2 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"55dcec2\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/2020\/04\/03\/theories-and-algorithms-2\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Theories<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-c945c22\" data-id=\"c945c22\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a660311 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a660311\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-3c41d91\" data-id=\"3c41d91\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ad3ba09 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"ad3ba09\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Probl%C3%A8me_de_flot_maximum\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-df7b822 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"df7b822\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b716659\" data-id=\"b716659\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-68641e0 elementor-widget elementor-widget-toggle\" data-id=\"68641e0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1091\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1091\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">I. Maximum flow<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1091\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1091\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/simplex-method-2\/\">Network simplex - see Simplex<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/ford-fulkerson-algorithm\/\">Ford-Fulkerson algorithm<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/algorithm-dedmonds-karp\/\">Edmonds-Karp algorithm<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/dinic-algorithm\/\">Dinic algorithm<\/a><\/li>\n<li><a href=\"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0020019078900169\" target=\"_blank\" rel=\"noopener\">MPM<\/a><\/li>\n<li><a href=\"https:\/\/link.springer.com\/chapter\/10.1007\/3-540-59408-6_49?error=cookies_not_supported&#038;code=23c67e9d-d1ea-402a-8927-3eec6b814318\" target=\"_blank\" rel=\"noopener\">Push-relabel algorithm<\/a><\/li>\n<li><a href=\"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0196677484710443\" target=\"_blank\" rel=\"noopener\">KRT<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/action\/cookieAbsent\" target=\"_blank\" rel=\"noopener\">Binary blocking flow algorithm<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/action\/cookieAbsent\" target=\"_blank\" rel=\"noopener\">Orlin<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1092\" class=\"elementor-tab-title\" data-tab=\"2\" role=\"button\" aria-controls=\"elementor-tab-content-1092\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">II. Maximum flow at minimum cost<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1092\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"2\" role=\"region\" aria-labelledby=\"elementor-tab-title-1092\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/simplex-method-2\/\">Network simplex - see Simplex<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/cycle-canceling-algorithm\/\">Cycle-canceling<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/busacker-gowen-algorithm\/\">Busacker &amp; Gowen algorithm<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/out-of-kilter-algorithm\/\">Out-of-kilter algorithm<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1093\" class=\"elementor-tab-title\" data-tab=\"3\" role=\"button\" aria-controls=\"elementor-tab-content-1093\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">III. Solvers<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1093\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"3\" role=\"region\" aria-labelledby=\"elementor-tab-title-1093\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/maximum-flow-resolution-with-excel\/\">Solve the maximum flow problem with Excel<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-50420d2b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"50420d2b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-60363235\" data-id=\"60363235\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-20b72e87 elementor-widget elementor-widget-text-editor\" data-id=\"20b72e87\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_83 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/#Flot-maximum\" >Maximum flow<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/#Definition-dun-reseau\" >Definition of a network<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/#Probleme-du-flot-maximum\" >Maximum flow problem<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/#Reduction-de-problemes\" >Reduction of problems<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/#Coupe-dun-reseau-et-capacite-residuelle\" >Cross-section of a network and residual capacity<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/#Trouver-un-flot-augmentant\" >Find an increasing flow<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Flot-maximum\"><\/span>Maximum flow<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p class=\"wp-block-paragraph\">The maximum flow to model a very large class of problems. Their interpretation corresponds to the circulation of physical flows on a network: electrical distribution, adduction network, routing of packets on the Internet, etc. This involves conveying the greatest possible quantity of material between a source <em><strong>s<\/strong><\/em> and a destination <em><strong>t<\/strong><\/em>.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\">Definition of a network<\/h2>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">A network is a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> oriented N=(V,A) with a positive valuation of its arcs. The valuation c(x,y) of an arc (x,y) is called the capacity of the arc. N has two particular vertices: a source s and a destination t. The other vertices are called intermediate nodes.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">A flow represents the routing of a flow of materials from a source <em><strong>s<\/strong><\/em> to a destination <em><strong>t<\/strong><\/em>. The flow is thus described by the quantity of material passing through each of the arcs of the network. This quantity must be less than the capacity of the arc, which thus limits the flow that can pass through it. In addition, it is not possible to store or produce matter at the intermediate nodes: a flow locally verifies a conservation law similar to Kirchhoff&#039;s laws in electricity.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">A flow F on a network N is a positive valuation of the arcs which satisfies the following two properties:<\/p>\n<p><\/p>\n<p><\/p>\n<ol class=\"wp-block-list\">\n<li>For any bow <em><strong>a \u2208 <em><strong>TO<\/strong><\/em>, 0 \u2264 <em><strong>F (a)<\/strong><\/em>\u2264<em><strong>that)<\/strong><\/em><\/strong><\/em><\/li>\n<li>For any intermediate summit <em><strong>x<\/strong><\/em>\u2208<em><strong>V <\/strong><\/em><strong>\\ { <em>s, t<\/em> }<\/strong>, \u2211<sub>y<\/sub> <em><strong>F (y, x)<\/strong><\/em> = \u2211<sub>y<\/sub> <em><strong>F (x, y)<\/strong><\/em><\/li>\n<\/ol>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">The sum F<sup>\u2013<\/sup><em><strong>(x) <\/strong><\/em><strong>=<\/strong><em><strong>\u2211<sub>y<\/sub>F (y, x)<\/strong><\/em> is the <em>inflow<\/em> at the top <em><strong>x<\/strong><\/em><br \/>The sum F<sup>+<\/sup><em><strong>(x) <\/strong><\/em><strong>=<\/strong><em><strong>\u2211<sub>y<\/sub>F (x, y)<\/strong><\/em> is the <em>outgoing flow<\/em> Summit <em><strong>x<\/strong><\/em><br \/>The <strong>value<\/strong> <strong>|<em> F <\/em>|<\/strong> of a flood <em><strong>F<\/strong><\/em> is defined as the outgoing flow minus the incoming flow in <em><strong>s<\/strong><\/em> : <strong>|<em> F <\/em>|<\/strong> = <em><strong>F<sup>+<\/sup>(s)<\/strong><\/em> \u2013 <em><strong>F<sup>\u2013<\/sup>(s).<\/strong><\/em><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Probleme-du-flot-maximum\"><\/span>Maximum flow problem<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">The classical maximum flow problem is a <a href=\"https:\/\/complex-systems-ai.com\/en\/help-with-the-decision\/linear-modeling\/\">linear problem<\/a>. We assume that the network has edges between any pair of vertices. If there is no capacity, it is fixed at 0. The objective function is the sum of the flows leaving the source or entering the sink. The lens function may vary depending on the lens.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">The basic constraints are identical whatever the objective function:<\/p>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>Capacity constraints: f (u, v) \u2264 c (u, v)<\/li>\n<li>Symmetry: f (u, v) = - f (v, u)<\/li>\n<li>Conservation of flows: the sum of the incoming flows is equal to the sum of the outgoing flows except for the source and the sink, the degree d (u) is called the difference between the outgoing and incoming flow from the vertex u: d (u) = 0 except for u = s and u = t.<\/li>\n<li>others<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Many problems can be traced back to a maximum flow problem. A <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/algorithm-naif-greedy-enumeration-2\/\">naive algorithm<\/a> is to repeat the following process until you get stuck. Find a path st where each arc af(e)<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Reduction-de-problemes\"><\/span>Reduction of problems<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\"><strong><em>Multi-source multi-well flow problem<\/em> <\/strong>: a fictitious source is connected to all the sources, the capacity of the edges depends on various criteria (capacity of the vertices, inflow-outflow constraints). The wells are connected to a fictitious well. This type of problem is usually a pairing problem.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\"><em><strong>Flow problem with capacity at the peaks<\/strong> <\/em>: the vertices are duplicated in the entering vertex and the outgoing vertex with an arc connecting them. The capacity of this arc is equal to the capacity of the top.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\"><em><strong>Problem of <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/\">shortest way<\/a><\/strong><\/em> : the source is the origin of the path and the sink with d (s) = 1 and d (t) = - 1. There are no capacity constraints. The cost of passage in all arcs is 1. We are looking for the minimum cost stream.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\">Network cut and residual capacity<\/h2>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">A cut (E, T) of a transport network N = (V, A) is a partition of V into E and T = VE such that s \u2208E and t\u2208T. We define the capacitance c (E, T) of the cross-section the sum of the capacitances of the arcs (u, v) with u in E and v in T. For any cross-section (E, T) and any flow f, | f | is increased by the capacity of the cut c (E, T).<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"has-text-align-justify wp-block-paragraph\">Remove a set of edges to disconnect t from s. Find a set to minimize the sum of the capacities of the arcs. A min cut is a partition of nodes (S, T) such that s is in S and t in T where c (E, T) is minimal. By definition, the min-cut problem has the same result as a maximum flow problem.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Given a network N = (V, A) and a flow f over N, we call residual capacity c<sub>f<\/sub> (u, v) = c (u, v) - f (u, v). Moreover, if the capacity of (v, u) is zero, c<sub>f<\/sub> (v, u) = f (u, v). The residual capacity is always positive or zero.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">The residual graph is the network N &#039;= (V, A) with the residual capacities for each arc of A. An increasing path is a path between s and t in the residual graph.<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-3659 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/residuel.png\" alt=\"maximum flow max flow problem minimum cut residual capacity increasing flow\" width=\"656\" height=\"215\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/residuel.png 656w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/residuel-300x98.png 300w\" sizes=\"(max-width: 656px) 100vw, 656px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">From the residual graph of a max flow, it is possible to find the solution of the min-cut problem (and vice versa). In the following graph, if you find a set of connected vertices from the vertex s, you find the set {s, 3,4,7} which is the set S for the min-cut problem.<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img decoding=\"async\" class=\"alignnone wp-image-6325 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/flow2.png\" alt=\"maximum flow max flow problem minimum cut residual capacity increasing flow\" width=\"541\" height=\"251\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/flow2.png 541w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/flow2-300x139.png 300w\" sizes=\"(max-width: 541px) 100vw, 541px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Trouver-un-flot-augmentant\"><\/span>Find an increasing flow<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Find a path st in the residual graph, it is called an increasing path. Once the path is selected, increase the flow along the arcs in the same direction as the standard graph, decrease the flow along the backward arcs.<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img decoding=\"async\" class=\"alignnone wp-image-6321 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/flow1.png\" alt=\"maximum flow max flow problem minimum cut residual capacity increasing flow\" width=\"806\" height=\"279\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/flow1.png 806w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/flow1-300x104.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/flow1-768x266.png 768w\" sizes=\"(max-width: 806px) 100vw, 806px\" \/><\/figure>\n<p><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Theories Home page Wiki I. Maximum flow Network simplex \u2013 see Simplex Ford-Fulkerson algorithm Edmonds-Karp algorithm Dinic algorithm MPM Push-relabel algorithm KRT Binary \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-3587","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3587","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=3587"}],"version-history":[{"count":37,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3587\/revisions"}],"predecessor-version":[{"id":20423,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3587\/revisions\/20423"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=3587"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}