{"id":4428,"date":"2016-08-24T10:08:15","date_gmt":"2016-08-24T09:08:15","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=4428"},"modified":"2022-12-03T23:00:11","modified_gmt":"2022-12-03T22:00:11","slug":"cycle-canceling-algorithm","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/algoritmo-de-cancelacion-de-ciclo\/","title":{"rendered":"Algoritmo de cancelaci\u00f3n de ciclo"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"4428\" class=\"elementor elementor-4428\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ee37c1c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ee37c1c\" 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-7521c7b\" data-id=\"7521c7b\" 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-a4f9db9 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a4f9db9\" 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\/problema-de-flujo-maximo\/\">\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\">Problema de flujo m\u00e1ximo<\/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-1a5a1e3\" data-id=\"1a5a1e3\" 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-a91a301 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a91a301\" 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-7488800\" data-id=\"7488800\" 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-470f2b6 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"470f2b6\" 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:\/\/algorithms.discrete.ma.tum.de\/\" 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-4de2eaa0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4de2eaa0\" 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-4bcef52\" data-id=\"4bcef52\" 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-5de0be8f elementor-widget elementor-widget-text-editor\" data-id=\"5de0be8f\" 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_82_2 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\/algoritmo-de-cancelacion-de-ciclo\/#Cycle-canceling-algorithme\" >Algoritmo de cancelaci\u00f3n de ciclo<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Cycle-canceling-algorithme\"><\/span>Algoritmo de cancelaci\u00f3n de ciclo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>La cancelaci\u00f3n del ciclo <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algoritmo<\/a> comienza con una resoluci\u00f3n de <a href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/\">flujo maximo<\/a>. Luego, iterativamente, el algoritmo busca un ciclo con un costo negativo (costo negativo si el borde se toma en la direcci\u00f3n opuesta al flujo) y aumenta el flujo en este ciclo. Cuando no hay m\u00e1s ciclos negativos, el algoritmo finaliza.<\/p>\n<p><\/p>\n<p>Ejemplo :<\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-4472 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca1.png\" alt=\"algoritmo de ciclo negativo de cancelaci\u00f3n de ciclo\" width=\"711\" height=\"368\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca1.png 711w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca1-300x155.png 300w\" sizes=\"(max-width: 711px) 100vw, 711px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p>vamos a construirlo <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a> brecha y busque un ciclo negativo:<\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-4477 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca2.png\" alt=\"algoritmo de ciclo negativo de cancelaci\u00f3n de ciclo\" width=\"772\" height=\"345\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca2.png 772w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca2-300x134.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca2-768x343.png 768w\" sizes=\"(max-width: 772px) 100vw, 772px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p>El ciclo 4-2-3-4 tiene un costo de -3 + 1 + 1 = -1, podemos saturarlo con un flujo de 2.<\/p>\n<p><\/p>\n<p>De manera similar con el ciclo 4-2-1-3-4 con un costo de -3-2 +2 +1 = -2, podemos saturarlo con un flujo de 1.<\/p>\n<p><\/p>\n<p>Ya no hay un ciclo negativo, finaliza el algoritmo.<\/p>\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>Problema de flujo m\u00e1ximo P\u00e1gina de inicio Wiki Algoritmo de cancelaci\u00f3n de ciclo El algoritmo de cancelaci\u00f3n de ciclo comienza con una resoluci\u00f3n de flujo m\u00e1xima. Entonces, iterativamente, el algoritmo busca... <\/p>","protected":false},"author":1,"featured_media":0,"parent":3587,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-4428","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4428","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=4428"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4428\/revisions"}],"predecessor-version":[{"id":18462,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4428\/revisions\/18462"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3587"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=4428"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}