{"id":15074,"date":"2022-04-16T22:14:50","date_gmt":"2022-04-16T21:14:50","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=15074"},"modified":"2024-02-13T07:55:31","modified_gmt":"2024-02-13T06:55:31","slug":"exo-darbre-couvrant","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/problema-del-arbol-de-expansion\/","title":{"rendered":"5 ejercicios corregidos para el problema del \u00e1rbol de expansi\u00f3n"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"15074\" class=\"elementor elementor-15074\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6f91136 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6f91136\" 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-7b861fa\" data-id=\"7b861fa\" 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-2dea3d5 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"2dea3d5\" 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\/teoria-de-grafos\/\">\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\u00eda de grafos<\/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-e4c9bde\" data-id=\"e4c9bde\" 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-6d11d26 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"6d11d26\" 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-745dadd\" data-id=\"745dadd\" 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-c1fb762 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"c1fb762\" 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:\/\/en.wikipedia.org\/wiki\/Graph_theory\" 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-f1faa4e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f1faa4e\" 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-f66ed88\" data-id=\"f66ed88\" 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-123db42 elementor-widget elementor-widget-text-editor\" data-id=\"123db42\" 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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8b855f4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8b855f4\" data-element_type=\"section\"><div class=\"elementor-container elementor-column-gap-default\"><div class=\"elementor-row\"><div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0b0cb7e\" data-id=\"0b0cb7e\" data-element_type=\"column\"><div class=\"elementor-column-wrap elementor-element-populated\"><div class=\"elementor-widget-wrap\"><div class=\"elementor-element elementor-element-b2fcdf3 elementor-widget elementor-widget-heading\" data-id=\"b2fcdf3\" data-element_type=\"widget\" data-widget_type=\"heading.default\"><div class=\"elementor-widget-container\"><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\/teoria-de-grafos\/problema-del-arbol-de-expansion\/#Exercices-corriges-probleme-darbre-couvrant\" >Ejercicios corregidos: problema del \u00e1rbol de expansi\u00f3n<\/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\/teoria-de-grafos\/problema-del-arbol-de-expansion\/#Exercice-1\" >Ejercicio 1<\/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\/teoria-de-grafos\/problema-del-arbol-de-expansion\/#Exercice-2\" >Ejercicio 2<\/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\/teoria-de-grafos\/problema-del-arbol-de-expansion\/#Exercice-3\" >Ejercicio 3<\/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\/teoria-de-grafos\/problema-del-arbol-de-expansion\/#Exercice-4\" >Ejercicio 4<\/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\/teoria-de-grafos\/problema-del-arbol-de-expansion\/#Exercice-5\" >Ejercicio 5<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-corriges-probleme-darbre-couvrant\"><\/span>Ejercicios corregidos: problema del \u00e1rbol de expansi\u00f3n<span class=\"ez-toc-section-end\"><\/span><\/h2><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/section><section class=\"elementor-section elementor-top-section elementor-element elementor-element-97371ee elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"97371ee\" data-element_type=\"section\"><div class=\"elementor-container elementor-column-gap-default\"><div class=\"elementor-row\"><div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8404c8d\" data-id=\"8404c8d\" data-element_type=\"column\"><div class=\"elementor-column-wrap elementor-element-populated\"><div class=\"elementor-widget-wrap\"><div class=\"elementor-element elementor-element-7b13bd7 elementor-widget elementor-widget-text-editor\" data-id=\"7b13bd7\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\"><div class=\"elementor-widget-container\"><div class=\"elementor-text-editor elementor-clearfix\"><p>La p\u00e1gina presenta varios ejercicios corregidos sobre problemas de teor\u00eda de grafos. Estos ejercicios se centran en el problema del \u00e1rbol de expansi\u00f3n.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"cubierta de \u00e1rboles\" width=\"97\" height=\"97\" title=\"\"><\/p><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/section>\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-f425aa0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f425aa0\" 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-eeb8a94\" data-id=\"eeb8a94\" 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-0c72477 elementor-widget elementor-widget-heading\" data-id=\"0c72477\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-1\"><\/span>Ejercicio 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-32ba3ba elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"32ba3ba\" 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-679b817\" data-id=\"679b817\" 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-e0a7bb3 elementor-widget elementor-widget-text-editor\" data-id=\"e0a7bb3\" 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>Hay 5 ciudades. El costo de construir una carretera directamente entre i y j es la entrada a(i,j) en la siguiente matriz. Una entrada indefinida indica que la carretera no se puede construir. Determine el costo m\u00ednimo para hacer que todas las ciudades sean accesibles entre s\u00ed.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-10638 size-full\" title=\"Ejercicios Corregidos: Spanning Tree 1\" src=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image5.png?resize=187%2C148\" alt=\"\u00e1rbol de expansi\u00f3n de teor\u00eda de grafos de ejercicio corregido\" width=\"187\" height=\"148\" data-recalc-dims=\"1\" \/><\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-40c4222 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"40c4222\" 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-c34a426\" data-id=\"c34a426\" 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-6aa50ef elementor-widget elementor-widget-toggle\" data-id=\"6aa50ef\" 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-1111\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1111\" 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\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1111\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1111\"><p>Ordenamos las aristas seg\u00fan los pesos: 12, 23, 13, 45, 25, 15, 24, 35, 14 (fila-columna). El algoritmo de Kruskal acepta los bordes 12, 23, luego rechaza el 13, luego acepta el 45, 25 y luego se detiene. Por lo tanto, el costo m\u00ednimo para construir la red de carreteras es 3 + 3 + 7 + 8 = 21.<\/p><\/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-4d82faf elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4d82faf\" 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-525a60e\" data-id=\"525a60e\" 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-fb4d9ac elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"fb4d9ac\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-316ca38 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"316ca38\" 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-77e2b69\" data-id=\"77e2b69\" 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-691c638 elementor-widget elementor-widget-heading\" data-id=\"691c638\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-2\"><\/span>Ejercicio 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-8f9f269 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8f9f269\" 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-ad03511\" data-id=\"ad03511\" 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-4c5aa1c elementor-widget elementor-widget-text-editor\" data-id=\"4c5aa1c\" 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>El profesor Herr Guerard propone un nuevo algoritmo de divide y vencer\u00e1s para calcular \u00e1rboles de expansi\u00f3n m\u00ednimos, que es el siguiente.<\/p><p>Dado un grafo G = (V, E), dividir el conjunto V de v\u00e9rtices en dos conjuntos V1 y V2 tales que |V1| y |V2| difieren como m\u00e1ximo en 1. Sea E1 el conjunto de aristas que inciden s\u00f3lo en los v\u00e9rtices de V1, y sea E2 el conjunto de aristas que inciden s\u00f3lo en los v\u00e9rtices de V2. Resuelva recursivamente un problema de \u00e1rbol de expansi\u00f3n m\u00ednimo en cada uno de los dos subgrafos G1 = (V1, E1) y G2 = (V2, E2). Finalmente, seleccione el borde de peso m\u00ednimo en E que cruza el corte V1, V2 y use este borde para unir los dos \u00e1rboles de expansi\u00f3n m\u00ednimos resultantes en un solo \u00e1rbol de expansi\u00f3n.<\/p><p>O argumenta que el algoritmo calcula correctamente un \u00e1rbol de expansi\u00f3n m\u00ednimo de G, o proporciona un ejemplo en el que falla el algoritmo. Encuentre un ejemplo donde funciona y donde no.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e0a26ea elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e0a26ea\" 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-d484d59\" data-id=\"d484d59\" 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-8a14d2a elementor-widget elementor-widget-toggle\" data-id=\"8a14d2a\" 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-1441\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1441\" 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\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1441\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1441\"><p>Afirmamos que el algoritmo fallar\u00e1. A continuaci\u00f3n se muestra un contraejemplo simple. El grafo G = (V, E) tiene cuatro v\u00e9rtices: {v1, v2, v3, v4} y se divide en subconjuntos G1 con V1 = {v1, v2} y G2 con V2 = {v3, v4}. El MST de G1 tiene un peso de 4, y el MST de G2 tiene un peso de 5, y el borde de peso m\u00ednimo que cruza el corte (V1, V2) tiene un peso de 1, en suma, el \u00e1rbol de expansi\u00f3n formado por el algoritmo propuesto sigue a {v2, v1 , v4, v3} que tiene un peso de 10. Por el contrario, es obvio que el MST de G sigue a {v4, v1, v2, v3} con un peso de 7. Por lo tanto, el algoritmo propuesto no logra obtener un MST.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-10639 size-full\" title=\"Ejercicios Corregidos: Spanning Tree 2\" src=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image6.png?resize=293%2C160\" alt=\"\u00e1rbol de expansi\u00f3n de teor\u00eda de grafos de ejercicio corregido\" width=\"293\" height=\"160\" data-recalc-dims=\"1\" \/><\/p><\/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-f0d6714 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f0d6714\" 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-cc3bcbf\" data-id=\"cc3bcbf\" 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-06df3bb elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"06df3bb\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-5e9c502 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5e9c502\" 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-426676a\" data-id=\"426676a\" 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-41682c0 elementor-widget elementor-widget-heading\" data-id=\"41682c0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-3\"><\/span>Ejercicio 3<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-314011d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"314011d\" 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-87122a5\" data-id=\"87122a5\" 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-46fed04 elementor-widget elementor-widget-text-editor\" data-id=\"46fed04\" 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>Demuestre que si G es un grafo ponderado y e es una arista cuyo peso es menor que cualquier otra arista, entonces e debe pertenecer a todo \u00e1rbol generador de peso m\u00ednimo para G.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-13f167d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"13f167d\" 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-4333229\" data-id=\"4333229\" 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-fe707aa elementor-widget elementor-widget-toggle\" data-id=\"fe707aa\" 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-2661\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2661\" 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\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2661\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2661\"><p>Supongamos que T es un \u00e1rbol generador de peso m\u00ednimo para G que no contiene la arista e. Considere entonces el gr\u00e1fico T+e. Este gr\u00e1fico debe contener un ciclo C que contiene la arista e. Sea f una arista de C diferente de e, y sea T*=T+e\u2212f. Entonces T* tambi\u00e9n es un \u00e1rbol de expansi\u00f3n para G, pero w(T*)=w(T+e\u2212f)=w(T)+w(e)\u2212w(f) &lt; w(T), a diferencia de T siendo un \u00e1rbol de expansi\u00f3n de peso m\u00ednimo. Por lo tanto, tal \u00e1rbol T (es decir, sin e) no puede existir.<\/p><\/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-c133761 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c133761\" 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-930d7f2\" data-id=\"930d7f2\" 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-4db5fe6 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"4db5fe6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-29caba2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"29caba2\" 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-5f2c120\" data-id=\"5f2c120\" 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-671d4fb elementor-widget elementor-widget-heading\" data-id=\"671d4fb\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-4\"><\/span>Ejercicio 4<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-a2f9f7c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a2f9f7c\" 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-b5a7886\" data-id=\"b5a7886\" 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-afa837f elementor-widget elementor-widget-text-editor\" data-id=\"afa837f\" 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>Muestre que si todos los pesos del grafo ponderado G son distintos, entonces hay un \u00fanico \u00e1rbol generador de peso m\u00ednimo para G.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4ec26b2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4ec26b2\" 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-85ba777\" data-id=\"85ba777\" 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-6f04d50 elementor-widget elementor-widget-toggle\" data-id=\"6f04d50\" 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-1161\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1161\" 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\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1161\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1161\"><p>La prueba imita algo la de la prueba del algoritmo de Kruskal. Supongamos que T es un \u00e1rbol generado por el algoritmo de Kruskal (de hecho, un momento de reflexi\u00f3n muestra que con las condiciones del problema, solo se podr\u00eda generar un \u00e1rbol de este tipo).<\/p><p>Afirmamos que no hay otros \u00e1rboles de expansi\u00f3n de peso m\u00ednimo para G. Supongamos (y mostraremos que esto conduce a una contradicci\u00f3n) que existen otros \u00e1rboles de expansi\u00f3n de peso m\u00ednimo y elija uno cualquiera, T&#039;. Supongamos entonces que e es la primera arista de T que no pertenece a T&#039;. Es decir, supongamos que las aristas de T, en el orden en que fueron sumadas para formar T, son e1, e2 , \u2026, ek , \u2026en\u22121 y que e = ek y para todo i &lt;k, ei \u2208T\u2019 .<\/p><p>Sea C el ciclo en T&#039;+ e que contiene a e. sea f una arista de C que no est\u00e1 en T&#039;. Observamos que por la naturaleza del algoritmo de Kruskal, el peso de f debe ser mayor que el peso de e. De hecho, en el momento en que colocamos e en T, f tambi\u00e9n estaba disponible y no habr\u00eda producido un ciclo (ya que todas las aristas de T hasta ese punto tambi\u00e9n est\u00e1n en T&#039;). Entonces si w(f) &lt;w(e), nous aurions utilis\u00e9 f \u00e0 ce stade. Alors maintenant l\u2019ensemble T*=T\u2019+e\u2212f est un arbre couvrant de poids inf\u00e9rieur \u00e0 T\u2019, une contradiction.<\/p><\/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-a6fcf04 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a6fcf04\" 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-3ed77dc\" data-id=\"3ed77dc\" 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-d679e99 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"d679e99\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-717ad0b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"717ad0b\" 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-6c2de70\" data-id=\"6c2de70\" 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-809f813 elementor-widget elementor-widget-heading\" data-id=\"809f813\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-5\"><\/span>Ejercicio 5<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-c352d2f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c352d2f\" 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-64ebd76\" data-id=\"64ebd76\" 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-a26c756 elementor-widget elementor-widget-text-editor\" data-id=\"a26c756\" 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>Considere un algoritmo de Kruskal &quot;invertido&quot; para calcular un MST. Inicialice T para que sea el conjunto de todos los bordes del gr\u00e1fico. Ahora considere los bordes de mayor a menor costo. Para cada borde, elim\u00ednelo de T si ese borde pertenece a un ciclo en T. Suponiendo que todos los costos de borde son distintos, \u00bfeste nuevo algoritmo calcula correctamente un MST?<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-64122ea elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"64122ea\" 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-a33abea\" data-id=\"a33abea\" 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-df34a85 elementor-widget elementor-widget-toggle\" data-id=\"df34a85\" 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-2341\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2341\" 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\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2341\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2341\"><p>S\u00ed. En el paso k (comenzando con ak = 1), el algoritmo considera la k-\u00e9sima ventaja de costo m\u00e1s grande. Si esta arista pertenece a un ciclo en el grafo restante T, entonces todas las aristas de este ciclo (y de hecho de T) deben tener un coste inferior al de la arista considerada. Por lo tanto, el borde no puede pertenecer al MST (seg\u00fan la pregunta anterior).<\/p><p>El algoritmo no puede terminar con T teniendo un ciclo, porque el algoritmo habr\u00eda considerado cada arista en dicho ciclo y habr\u00eda eliminado la arista de mayor costo cuando consider\u00f3 esa arista. El algoritmo tampoco puede terminar con T desconectada, porque las aristas solo se eliminan cuando pertenecen a un ciclo, y desconectar una arista que pertenece a un ciclo no desconecta el gr\u00e1fico. Por lo tanto, el algoritmo termina siendo T un \u00e1rbol de expansi\u00f3n.<\/p><p>Es el MST porque todas las aristas que se han borrado tienen la propiedad de no pertenecer al MST. Dado que los \u00fanicos bordes que podr\u00edan pertenecer al MST son los restantes y, de hecho, definen un \u00e1rbol de expansi\u00f3n, debe ser el MST.<\/p><\/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<\/div>","protected":false},"excerpt":{"rendered":"<p>P\u00e1gina de inicio de Graph Theory Wiki Ejercicios corregidos: problema del \u00e1rbol de expansi\u00f3n La p\u00e1gina presenta varios ejercicios corregidos sobre problemas de teor\u00eda de grafos. \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":2204,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-15074","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/15074","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=15074"}],"version-history":[{"count":6,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/15074\/revisions"}],"predecessor-version":[{"id":20541,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/15074\/revisions\/20541"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2204"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=15074"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}