{"id":10631,"date":"2020-11-05T20:29:39","date_gmt":"2020-11-05T19:29:39","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=10631"},"modified":"2022-12-03T23:05:30","modified_gmt":"2022-12-03T22:05:30","slug":"corrected-exercises-spanning-tree","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/arbol-de-expansion-de-ejercicios-corregidos\/","title":{"rendered":"Ejercicios corregidos: \u00e1rbol de expansi\u00f3n"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"10631\" class=\"elementor elementor-10631\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5d4a56d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5d4a56d\" 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-f039029\" data-id=\"f039029\" 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-c4d3fc3 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"c4d3fc3\" 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-87f545c\" data-id=\"87f545c\" 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-72acfad elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"72acfad\" 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-6dfa5fd\" data-id=\"6dfa5fd\" 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-8e7f082 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"8e7f082\" 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-8b855f4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8b855f4\" 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-0b0cb7e\" data-id=\"0b0cb7e\" 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-b2fcdf3 elementor-widget elementor-widget-heading\" data-id=\"b2fcdf3\" 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<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\/arbol-de-expansion-de-ejercicios-corregidos\/#Corrected-exercises-about-spanning-tree\" >Ejercicios corregidos sobre \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\/arbol-de-expansion-de-ejercicios-corregidos\/#Exercise-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\/arbol-de-expansion-de-ejercicios-corregidos\/#Exercise-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\/arbol-de-expansion-de-ejercicios-corregidos\/#Exercise-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\/arbol-de-expansion-de-ejercicios-corregidos\/#Exercise-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\/arbol-de-expansion-de-ejercicios-corregidos\/#Exercise-5\" >Ejercicio 5<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Corrected-exercises-about-spanning-tree\"><\/span>Ejercicios corregidos sobre \u00e1rbol de expansi\u00f3n<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-97371ee elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"97371ee\" 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-8404c8d\" data-id=\"8404c8d\" 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-7b13bd7 elementor-widget elementor-widget-text-editor\" data-id=\"7b13bd7\" 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>La p\u00e1gina presenta varios ejercicios corregidos sobre problemas de teor\u00eda de grafos. Estos ejercicios tratan sobre problemas de \u00e1rbol de expansi\u00f3n.<\/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-c4d6580 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c4d6580\" 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-2ff6c14\" data-id=\"2ff6c14\" 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-0a8d162 elementor-widget elementor-widget-text-editor\" data-id=\"0a8d162\" 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<h2><span class=\"ez-toc-section\" id=\"Exercise-1\"><\/span><strong><b>Ejercicio 1<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Hay 5 ciudades. El costo de construir una carretera directamente entre i y j es la entrada a<sub>yo, j<\/sub>\u00a0en la matriz a continuaci\u00f3n. Una entrada indefinida indica que la carretera no se puede construir. Determine el menor costo de hacer que todas las ciudades sean accesibles entre s\u00ed.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-10638 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image5.png\" alt=\"\u00e1rbol de expansi\u00f3n de teor\u00eda de grafos de ejercicio corregido\" width=\"187\" height=\"148\" title=\"\"><\/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-553bd32 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"553bd32\" 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-e893e57\" data-id=\"e893e57\" 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-e771cb4 elementor-widget elementor-widget-toggle\" data-id=\"e771cb4\" 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-2421\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2421\" 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-2421\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2421\"><p>Ordenamos los bordes seg\u00fan los pesos: 12, 23, 13, 45, 25, 15, 24, 35, 14 (columna sin procesar). El algoritmo de Kruskal acepta los bordes 12, 23, luego rechaza 13, luego acepta 45, 25 y luego se detiene. Por lo tanto, el menor costo 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-89218dc elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"89218dc\" 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-42ab47f\" data-id=\"42ab47f\" 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-d4013f0 elementor-widget elementor-widget-text-editor\" data-id=\"d4013f0\" 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<h2><span class=\"ez-toc-section\" id=\"Exercise-2\"><\/span><strong><b>Ejercicio 2<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>El profesor Herr Guerard propone una nueva <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/divide-y-venceras\/\">divide y conquistaras<\/a> algoritmo para calcular \u00e1rboles de expansi\u00f3n m\u00ednimos, que es el siguiente.<\/p><p>Dado un gr\u00e1fico G = (V, E), divida el conjunto V de v\u00e9rtices en dos conjuntos V<sub>1<\/sub>\u00a0y V<sub>2<\/sub>\u00a0tal que | V<sub>1<\/sub>| y | V<sub>2<\/sub>| difieren como m\u00e1ximo en 1. Sea E1 el conjunto de aristas que inciden solo en los v\u00e9rtices de V<sub>1<\/sub>y deja que E<sub>2<\/sub>\u00a0ser el conjunto de aristas que inciden solo en v\u00e9rtices en V<sub>2<\/sub>. Resuelva de forma recursiva un problema de \u00e1rbol de expansi\u00f3n m\u00ednimo en cada uno de los dos subgrafos G<sub>1<\/sub>\u00a0= (V<sub>1<\/sub>, E<sub>1<\/sub>) y G<sub>2<\/sub>\u00a0= (V<sub>2<\/sub>, E<sub>2<\/sub>). 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 el algoritmo falla. Encontr\u00e9 un ejemplo de d\u00f3nde funciona y d\u00f3nde no funciona.<\/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-9b85f85 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9b85f85\" 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-4940395\" data-id=\"4940395\" 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-953dc96 elementor-widget elementor-widget-toggle\" data-id=\"953dc96\" 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-1561\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1561\" 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-1561\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1561\"><p>Afirmamos que el algoritmo fallar\u00e1. A continuaci\u00f3n se muestra un ejemplo de contador simple. El gr\u00e1fico G = (V, E) tiene cuatro v\u00e9rtices: {v<sub>1<\/sub>, v<sub>2<\/sub>, v<sub>3<\/sub>, v<sub>4<\/sub>}, y se divide en subconjuntos G<sub>1<\/sub>\u00a0con V<sub>1<\/sub>\u00a0= {v<sub>1<\/sub>, v<sub>2<\/sub>} y G<sub>2<\/sub>\u00a0con V<sub>2<\/sub>\u00a0= {v<sub>3<\/sub>, v<sub>4<\/sub>}. T\u00e9 <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/cubriendo-arboles\/\">ETS<\/a> de G<sub>1<\/sub>\u00a0tiene peso 4, y el MST de G<sub>2<\/sub>\u00a0tiene un peso de 5 y el borde de peso m\u00ednimo que cruza el corte (V<sub>1<\/sub>, V<sub>2<\/sub>) tiene peso 1, en suma, el \u00e1rbol de expansi\u00f3n que se forma mediante el algoritmo propuesto sigue {v<sub>2<\/sub>, v<sub>1<\/sub>, v<sub>4<\/sub>, v<sub>3<\/sub>} que tiene peso 10. Por el contrario, es obvio que el MST de G sigue {v<sub>4<\/sub>, v<sub>1<\/sub>, v<sub>2<\/sub>, v<sub>3<\/sub>} con peso 7. Por lo tanto, el algoritmo propuesto no logra obtener un MST.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-10639 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image6.png\" alt=\"\u00e1rbol de expansi\u00f3n de teor\u00eda de grafos de ejercicio corregido\" width=\"293\" height=\"160\" title=\"\"><\/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-9ebac46 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9ebac46\" 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-22161fc\" data-id=\"22161fc\" 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-c638723 elementor-widget elementor-widget-text-editor\" data-id=\"c638723\" 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<h2><span class=\"ez-toc-section\" id=\"Exercise-3\"><\/span><strong><b>Ejercicio 3<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Demuestre que si G es una gr\u00e1fica ponderada ye es una arista cuyo peso es menor que el de cualquier otra arista, entonces e debe pertenecer a cada \u00e1rbol de expansi\u00f3n 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-4f1e21e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4f1e21e\" 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-6ac80ee\" data-id=\"6ac80ee\" 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-1004aa2 elementor-widget elementor-widget-toggle\" data-id=\"1004aa2\" 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-1671\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1671\" 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-1671\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1671\"><p>Suponga que T es un \u00e1rbol de expansi\u00f3n de peso m\u00ednimo para G que no contiene el borde e. Luego considere la gr\u00e1fica T + e. Este gr\u00e1fico debe contener un ciclo C que contenga el borde e. Sea f una arista de C diferente de e, y establezca T * = T + e - f. Entonces T * es tambi\u00e9n un \u00e1rbol de expansi\u00f3n para G, pero w (T *) = w (T + e - f) = w (T) + w (e) \u2212w (f) &lt;w (T), contrario a T siendo un \u00e1rbol de expansi\u00f3n de peso m\u00ednimo. Por 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-8c33eb0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8c33eb0\" 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-1e105ba\" data-id=\"1e105ba\" 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-10a8c01 elementor-widget elementor-widget-text-editor\" data-id=\"10a8c01\" 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<h2><span class=\"ez-toc-section\" id=\"Exercise-4\"><\/span><strong><b>Ejercicio 4<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Demuestre que si todos los pesos del gr\u00e1fico ponderado G son distintos, entonces existe un \u00e1rbol de expansi\u00f3n de peso m\u00ednimo \u00fanico 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-df1dd03 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"df1dd03\" 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-594391a\" data-id=\"594391a\" 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-124f6c1 elementor-widget elementor-widget-toggle\" data-id=\"124f6c1\" 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-1911\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1911\" 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-1911\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1911\"><p>La prueba imita un poco a la prueba del algoritmo de Kruskal. Supongamos que T es un \u00e1rbol generado por el algoritmo de Kruskal (de hecho, un momento de pensamiento muestra que con las condiciones del problema, solo se podr\u00eda generar uno de esos \u00e1rboles).<\/p><p>Afirmamos que no hay otros \u00e1rboles de expansi\u00f3n de peso m\u00ednimo para G. Suponga (y mostraremos que esto conduce a una contradicci\u00f3n) que hay otros \u00e1rboles de expansi\u00f3n de peso m\u00ednimo y elija uno, T &#039;. Entonces suponga que e es el primer borde de T que no est\u00e1 en T &#039;. En otras palabras, suponga que las aristas de T, en el orden en que se agregaron para formar T, son e<sub>1<\/sub>, e<sub>2 <\/sub>,\u2026, E<sub>k<\/sub>\u00a0,\u2026 E<sub>n - 1 <\/sub>y que e = e<sub>k<\/sub>\u00a0y por todo yo &lt;k, e<sub>I<\/sub>\u00a0\u2208T &#039;.<\/p><p>Sea C el ciclo en T &#039;+ e que contiene 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. Esto se debe a que 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), we would have used f at that juncture. So now set T*=T\u2019+e\u2212f is a spanning tree of weight less than T\u2019, a 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-09d6a5a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"09d6a5a\" 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-ba754d2\" data-id=\"ba754d2\" 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-51fd398 elementor-widget elementor-widget-text-editor\" data-id=\"51fd398\" 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<h2><span class=\"ez-toc-section\" id=\"Exercise-5\"><\/span><strong><b>Ejercicio 5<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><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 los bordes 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-a4543a3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a4543a3\" 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-020ed5e\" data-id=\"020ed5e\" 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-3fadfbb elementor-widget elementor-widget-toggle\" data-id=\"3fadfbb\" 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-6671\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-6671\" 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-6671\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-6671\"><p>Si lo hace. En la etapa k (comenzando ak = 1), el algoritmo considera la k-\u00e9sima ventaja de costo m\u00e1s grande. Si ese borde pertenece a un ciclo en el gr\u00e1fico T restante, entonces todos los bordes en ese ciclo (y de hecho en T) deben tener un costo menor que el borde que se est\u00e1 considerando. Por tanto, el borde no puede pertenecer al MST (por la pregunta anterior).<\/p><p>El algoritmo no puede terminar con T teniendo un ciclo, ya que el algoritmo habr\u00eda considerado cada borde en dicho ciclo y habr\u00eda eliminado el borde del mayor costo cuando consider\u00f3 ese borde. El algoritmo tampoco puede terminar con la desconexi\u00f3n de T, ya que los bordes solo se eliminan cuando pertenecen a un ciclo, y la desconexi\u00f3n de un borde que pertenece a un ciclo no desconecta el gr\u00e1fico. Por tanto, el algoritmo termina siendo T un \u00e1rbol de expansi\u00f3n.<\/p><p>Es el MST porque todos los bordes que se eliminaron tienen la propiedad de que no pueden pertenecer al MST. Dado que los \u00fanicos bordes que podr\u00edan pertenecer al MST son los que quedan, 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>Graph Theory Home Wiki Ejercicios corregidos sobre el \u00e1rbol de expansi\u00f3n La p\u00e1gina presenta varios ejercicios corregidos sobre problemas de teor\u00eda de grafos. Esos ejercicios son sobre ... <\/p>","protected":false},"author":1,"featured_media":0,"parent":2204,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"elementor_header_footer","meta":{"footnotes":""},"class_list":["post-10631","page","type-page","status-publish","hentry"],"amp_enabled":false,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/10631","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=10631"}],"version-history":[{"count":1,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/10631\/revisions"}],"predecessor-version":[{"id":19065,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/10631\/revisions\/19065"}],"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=10631"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}