{"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\/es\/problema-de-flujo-maximo\/","title":{"rendered":"Problema de flujo m\u00e1ximo 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\/es\/2020\/04\/03\/teorias-y-algoritmos-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\">Teor\u00edas<\/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\/es\/\">\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\">Pagina de inicio<\/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. Flujo m\u00e1ximo<\/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\/es\/programacion-lineal\/metodo-simplex\/\">Red simplex: consulte Simplex<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/ford-fulkerson-algoritmo-2\/\">Algoritmo de Ford-Fulkerson<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/algoritmo-dedmonds-karp\/\">Algoritmo de Edmonds-Karp<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/algoritmo-dinic\/\">Algoritmo dinic<\/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\">Algoritmo push-reetiquetado<\/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\">Algoritmo de flujo de bloqueo binario<\/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. Caudal m\u00e1ximo al m\u00ednimo coste<\/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\/es\/programacion-lineal\/metodo-simplex\/\">Red simplex: consulte Simplex<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/algoritmo-de-cancelacion-de-ciclo\/\">Cancelaci\u00f3n de ciclo<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/algoritmo-busacker-gowen\/\">Algoritmo de Busacker &amp; Gowen<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/algoritmo-fuera-de-lugar\/\">Algoritmo fuera de lugar<\/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. Solucionadores<\/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\/es\/problema-de-flujo-maximo\/maxima-resolucion-de-flujo-con-excel\/\">Resuelva el problema de flujo m\u00e1ximo con 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_84 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\">Contenido<\/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=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/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\/es\/problema-de-flujo-maximo\/#Flot-maximum\" >Flujo maximo<\/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\/es\/problema-de-flujo-maximo\/#Definition-dun-reseau\" >Definici\u00f3n de una red<\/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\/es\/problema-de-flujo-maximo\/#Probleme-du-flot-maximum\" >Problema de flujo m\u00e1ximo<\/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\/es\/problema-de-flujo-maximo\/#Reduction-de-problemes\" >Reducci\u00f3n de problemas<\/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\/es\/problema-de-flujo-maximo\/#Coupe-dun-reseau-et-capacite-residuelle\" >Corte de red y capacidad residual<\/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\/es\/problema-de-flujo-maximo\/#Trouver-un-flot-augmentant\" >Encuentra un flujo creciente<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Flot-maximum\"><\/span>Flujo maximo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p class=\"wp-block-paragraph\">El flujo m\u00e1ximo para modelar una clase muy grande de problemas. Su interpretaci\u00f3n corresponde a la circulaci\u00f3n de flujos f\u00edsicos en una red: distribuci\u00f3n el\u00e9ctrica, red de aducci\u00f3n, enrutamiento de paquetes en Internet, etc. Esto implica transportar la mayor cantidad posible de material entre una fuente <em><strong>s<\/strong><\/em> y un destino <em><strong>t<\/strong><\/em>.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Definition-dun-reseau\"><\/span>Definici\u00f3n de una red<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Una red es un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a> orientada N=(V,A) con una valoraci\u00f3n positiva de sus arcos. La valoraci\u00f3n c(x,y) de un arco (x,y) se llama capacidad del arco. N tiene dos v\u00e9rtices particulares: un origen s y un destino t. Los otros v\u00e9rtices se denominan nodos intermedios.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Un flujo representa el enrutamiento de un flujo de materiales desde una fuente. <em><strong>s<\/strong><\/em> a un destino <em><strong>t<\/strong><\/em>. El flujo se describe as\u00ed por la cantidad de material que pasa por cada uno de los arcos de la red. Esta cantidad debe ser menor que la capacidad del arco, lo que limita el flujo que puede atravesarlo. Adem\u00e1s, no es posible almacenar o producir materia en los nodos intermedios: un flujo verifica localmente una ley de conservaci\u00f3n similar a las leyes de Kirchhoff en electricidad.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Un flujo F en una red N es una valoraci\u00f3n positiva de los arcos que satisface las siguientes dos propiedades:<\/p>\n<p><\/p>\n<p><\/p>\n<ol class=\"wp-block-list\">\n<li>Para cualquier arco <em><strong>un \u2208 <em><strong>PARA<\/strong><\/em>, 0 \u2264 <em><strong>F (a)<\/strong><\/em>\u2264<em><strong>ese)<\/strong><\/em><\/strong><\/em><\/li>\n<li>Para cualquier cumbre intermedia <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\">La suma F<sup>\u2013<\/sup><em><strong>(X) <\/strong><\/em><strong>=<\/strong><em><strong>\u2211<sub>y<\/sub>F (y, x)<\/strong><\/em> es el <em>afluencia<\/em> en la cima <em><strong>X<\/strong><\/em><br \/>La suma F<sup>+<\/sup><em><strong>(X) <\/strong><\/em><strong>=<\/strong><em><strong>\u2211<sub>y<\/sub>F (x, y)<\/strong><\/em> es el <em>flujo saliente<\/em> Cumbre <em><strong>X<\/strong><\/em><br \/>los <strong>valor<\/strong> <strong>|<em> F <\/em>|<\/strong> de una inundaci\u00f3n <em><strong>F<\/strong><\/em> se define como el flujo saliente menos el flujo entrante en <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>Problema de flujo m\u00e1ximo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">El problema cl\u00e1sico de flujo m\u00e1ximo es un <a href=\"https:\/\/complex-systems-ai.com\/es\/ayuda-con-la-decision\/modelado-lineal\/\">problema lineal<\/a>. Suponemos que la red tiene aristas entre cualquier par de v\u00e9rtices. Si no hay capacidad, se fija en 0. La funci\u00f3n objetivo es la suma de los flujos que salen de la fuente o entran en el sumidero. La funci\u00f3n de la lente puede variar dependiendo de la lente.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Las restricciones b\u00e1sicas son id\u00e9nticas cualquiera que sea la funci\u00f3n objetivo:<\/p>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>Restricciones de capacidad: f (u, v) \u2264 c (u, v)<\/li>\n<li>Simetr\u00eda: f (u, v) = - f (v, u)<\/li>\n<li>Conservaci\u00f3n de caudales: la suma de los caudales entrantes es igual a la suma de los caudales salientes a excepci\u00f3n de la fuente y el sumidero, el grado d (u) se llama la diferencia entre el caudal saliente y entrante del v\u00e9rtice u: d ( u) = 0 excepto para u = sy u = t.<\/li>\n<li>otros<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Muchos problemas se remontan a un problema de flujo m\u00e1ximo. A <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/algoritmo-naif-codicia-enumeracion\/\">algoritmo ingenuo<\/a> es repetir el siguiente proceso hasta que te quedes atascado. Encuentre un camino st donde cada arco 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>Reducci\u00f3n de problemas<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\"><strong><em>Problema de flujo de m\u00faltiples fuentes y m\u00faltiples pozos<\/em> <\/strong>: una fuente ficticia est\u00e1 conectada a todas las fuentes, la capacidad de los bordes depende de varios criterios (capacidad de los v\u00e9rtices, restricciones de entrada-salida). Los pozos est\u00e1n conectados a un pozo ficticio. Este tipo de problema suele ser un problema de emparejamiento.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\"><em><strong>Problema de flujo con capacidad en los picos<\/strong> <\/em>: los v\u00e9rtices se duplican en el v\u00e9rtice de entrada y el v\u00e9rtice de salida con un arco que los conecta. La capacidad de este arco es igual a la capacidad de la tapa.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\"><em><strong>Problema de <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/\">camino m\u00e1s corto<\/a><\/strong><\/em> : la fuente es el origen de la ruta y el sumidero con d (s) = 1 y d (t) = - 1. No hay limitaciones de capacidad. El costo de paso en todos los arcos es 1. Buscamos el flujo de costo m\u00ednimo.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Coupe-dun-reseau-et-capacite-residuelle\"><\/span>Corte de red y capacidad residual<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Un corte (E, T) de una red de transporte N = (V, A) es una partici\u00f3n de V en E y T = VE tal que s \u2208E y t\u2208T. Definimos la capacitancia c (E, T) de la secci\u00f3n transversal la suma de las capacitancias de los arcos (u, v) con u en E yv en T. Para cualquier secci\u00f3n transversal (E, T) y cualquier flujo f, | f | se incrementa por la capacidad del corte c (E, T).<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"has-text-align-justify wp-block-paragraph\">Quite un juego de bordes para desconectar t de s. Encuentre un conjunto para minimizar la suma de las capacidades de los arcos. Un corte m\u00ednimo es una partici\u00f3n de nodos (S, T) tal que s est\u00e1 en S yt en T donde c (E, T) es m\u00ednimo. Por definici\u00f3n, el problema de corte m\u00ednimo tiene el mismo resultado que un problema de flujo m\u00e1ximo.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Dada una red N = (V, A) y un flujo f sobre N, llamamos capacidad residual c<sub>F<\/sub> (u, v) = c (u, v) - f (u, v). Adem\u00e1s, si la capacidad de (v, u) es cero, c<sub>F<\/sub> (v, u) = f (u, v). La capacidad residual es siempre positiva o nula.<\/p>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">El gr\u00e1fico residual es la red N &#039;= (V, A) con las capacidades residuales para cada arco de A. Una trayectoria creciente es una trayectoria entre syt en el gr\u00e1fico residual.<\/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=\"flujo m\u00e1ximo problema de flujo m\u00e1ximo corte m\u00ednimo capacidad residual flujo creciente\" 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\">A partir del gr\u00e1fico residual de un flujo m\u00e1ximo, es posible encontrar la soluci\u00f3n del problema de corte m\u00ednimo (y viceversa). En la siguiente gr\u00e1fica, si encuentra un conjunto de v\u00e9rtices conectados desde el v\u00e9rtice s, encuentra el conjunto {s, 3, 4, 7} que es el conjunto S para el problema de corte m\u00ednimo.<\/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=\"flujo m\u00e1ximo problema de flujo m\u00e1ximo corte m\u00ednimo capacidad residual flujo creciente\" 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>Encuentra un flujo creciente<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Encuentre un camino st en el gr\u00e1fico residual, se llama camino creciente. Una vez que se selecciona la ruta, aumente el flujo a lo largo de los arcos en la misma direcci\u00f3n que el gr\u00e1fico est\u00e1ndar, disminuya el flujo a lo largo de los arcos hacia atr\u00e1s.<\/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=\"flujo m\u00e1ximo problema de flujo m\u00e1ximo corte m\u00ednimo capacidad residual flujo creciente\" 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>Teor\u00edas P\u00e1gina de inicio Wiki I. Flujo m\u00e1ximo Red s\u00edmplex \u2013 ver S\u00edmplex Algoritmo Ford-Fulkerson Algoritmo Edmonds-Karp Algoritmo Dinic MPM Algoritmo Push-relabel KRT Binario \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\/es\/wp-json\/wp\/v2\/pages\/3587","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=3587"}],"version-history":[{"count":37,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3587\/revisions"}],"predecessor-version":[{"id":20423,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3587\/revisions\/20423"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=3587"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}