{"id":2932,"date":"2015-04-03T10:04:49","date_gmt":"2015-04-03T14:04:49","guid":{"rendered":"http:\/\/www.acarlstein.com\/?p=2932"},"modified":"2015-04-03T15:32:31","modified_gmt":"2015-04-03T19:32:31","slug":"maximum-flow","status":"publish","type":"post","link":"http:\/\/blog.acarlstein.com\/?p=2932","title":{"rendered":"Maximum Flow"},"content":{"rendered":"<p><strong>Definition<\/strong><\/p>\n<ul>\n<li>The capacity constrain indicate that a given capacity must not be exceed by the flow from one vertex to another.<\/li>\n<li>The skew symmetry (a notational convenience) indicate that the flow from vertex <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?u\" alt=\"u\" align=\"absmiddle\" \/> to vertex <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?v\" alt=\"v\" align=\"absmiddle\" \/> is the negative of the flow in the reverse direction.<\/li>\n<li>The flow-conservation property indicate that the total flow out of a vertex other than the source <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?S\" alt=\"S\" align=\"absmiddle\" \/> or sink <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?t\" alt=\"t\" align=\"absmiddle\" \/> is 0<\/li>\n<li>The total positive flow leaving a vertex is defined symmetrically<\/li>\n<li>The total positive flow leaving the vertex minus the total positive flow entering a vertex is the\u00a0 total net-flow at a vertex<\/li>\n<li>The total positive flow entering a vertex other than the source <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?S\" alt=\"S\" align=\"absmiddle\" \/> or sink <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?t\" alt=\"t\" align=\"absmiddle\" \/> must be equal to the positive flow leaving that vertex.<\/li>\n<\/ul>\n<p><strong>Examples<\/strong><\/p>\n<ul>\n<li><a title=\"The Ford-Fulkerson Method\" href=\"http:\/\/www.acarlstein.com\/?p=2935\">The Ford-Fulkerson Method<\/a><\/li>\n<li>The Edmonds-Karp Algorithm<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n\n<script>\nvar zbPregResult = '0';\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>Definition The capacity constrain indicate that a given capacity must not be exceed by the flow from one vertex to another. The skew symmetry (a notational convenience) indicate that the flow from vertex to vertex is the negative of the flow in the reverse direction. The flow-conservation property indicate that the total flow out of [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19,218],"tags":[1265],"class_list":["post-2932","post","type-post","status-publish","format-standard","hentry","category-programming","category-algorithms-programming","tag-maximum-flow"],"_links":{"self":[{"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/posts\/2932","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2932"}],"version-history":[{"count":2,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/posts\/2932\/revisions"}],"predecessor-version":[{"id":2953,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/posts\/2932\/revisions\/2953"}],"wp:attachment":[{"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2932"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2932"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2932"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}