{"id":2621,"date":"2016-02-16T15:07:03","date_gmt":"2016-02-16T14:07:03","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=2621"},"modified":"2022-12-03T22:59:00","modified_gmt":"2022-12-03T21:59:00","slug":"arbres-couvrants","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/cubriendo-arboles\/","title":{"rendered":"Cubriendo \u00e1rboles"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"2621\" class=\"elementor elementor-2621\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-821effe elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"821effe\" 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-0db454e\" data-id=\"0db454e\" 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-2936e36 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"2936e36\" 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-f99ae6d\" data-id=\"f99ae6d\" 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-b7408de elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"b7408de\" 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-734a68c\" data-id=\"734a68c\" 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-bf45e4f elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"bf45e4f\" 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\/Arbre_couvrant\" 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-6491a7b6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6491a7b6\" 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-6454cc8f\" data-id=\"6454cc8f\" 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-25846f91 elementor-widget elementor-widget-text-editor\" data-id=\"25846f91\" 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<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\/cubriendo-arboles\/#Arbres-couvrants\" >Cubriendo \u00e1rboles<\/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\/cubriendo-arboles\/#Algorithme-de-Kruskal\" >Algoritmo de Kruskal<\/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\/cubriendo-arboles\/#i\" >\u00a0<\/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\/cubriendo-arboles\/#Algorithme-de-Prim\" >Algoritmo de Prim<\/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\/cubriendo-arboles\/#Kruskal-pas-a-pas\" >Kruskal paso a paso<\/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\/cubriendo-arboles\/#Prim-pas-a-pas\" >Prim paso a paso<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Arbres-couvrants\"><\/span>Cubriendo \u00e1rboles<span class=\"ez-toc-section-end\"><\/span><\/h2><div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Se dice que un subgrafo de G cubre si contiene todos los v\u00e9rtices de G.<\/div><div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Un subgrafo de expansi\u00f3n no es necesariamente conexo. A <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/arboles-y-arboles\/\">\u00e1rbol<\/a> el cubrimiento de G es un subgrafo cubriente de G, y este subgrafo es un \u00e1rbol.<\/div><p>Para minimizar el costo de las redes el\u00e9ctricas, conexiones de cableado, tuber\u00edas, reconocimiento autom\u00e1tico de voz, etc., utilizamos algoritmos que construyen gradualmente un \u00e1rbol de expansi\u00f3n (o m\u00e1s de estos \u00e1rboles) como pasos intermedios en el proceso de b\u00fasqueda de \u00e1rboles de cobertura m\u00ednima. .<\/p><p>Internet y muchas otras redes de telecomunicaciones tienen enlaces de transmisi\u00f3n que conectan los nodos en una topolog\u00eda de malla que incluye algunos bucles. Para evitar bucles de puente y bucles de enrutamiento, muchos protocolos de enrutamiento dise\u00f1ados para tales redes requieren que cada enrutador recuerde un \u00e1rbol de expansi\u00f3n.<\/p><p style=\"text-align: justify;\"><img decoding=\"async\" class=\"aligncenter wp-image-2627 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre9.png\" alt=\"cubierta de \u00e1rboles\" width=\"233\" height=\"151\" title=\"\"><\/p><p style=\"text-align: justify;\">Es f\u00e1cil construir una cubierta para \u00e1rboles:<\/p><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><ul style=\"text-align: justify;\"><li>siempre que no hayamos sumado n-1 aristas a G&#039;, siendo n el n\u00famero de v\u00e9rtices de la <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a>, elegimos una arista de G de tal manera que su suma no cree un ciclo en G&#039;.<\/li><li>siempre que el n\u00famero de aristas restantes sea mayor que n-1, eliminamos una arista de G de modo que G siempre est\u00e9 conectado.<\/li><\/ul><\/div><p style=\"text-align: justify;\">El problema de los \u00e1rboles de expansi\u00f3n se utiliza ampliamente en el contexto de los bordes ponderados.<\/p><div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Esto se conoce como \u00e1rbol de expansi\u00f3n de peso m\u00ednimo. Este problema es un problema de creaci\u00f3n de red: <strong>no<\/strong> lugares para conectar, conocemos los costos de conectar un lugar a otro, buscamos conectar todos los lugares al menor costo.<\/div><p style=\"text-align: justify;\">Para hacer un \u00e1rbol de expansi\u00f3n de peso m\u00ednimo, estableceremos dos algoritmos codiciosos.<\/p><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Algorithme-de-Kruskal\"><\/span>Algoritmo de Kruskal<span class=\"ez-toc-section-end\"><\/span><\/h2><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p>Al principio, el gr\u00e1fico G &#039;contiene solo los v\u00e9rtices de G y tenemos una cola vac\u00eda (Fifo) <strong>F <\/strong>:<\/p><ul style=\"text-align: justify;\"><li>para cada v\u00e9rtice <strong>v<\/strong> por G<ul><li>agregar <strong>v<\/strong> Para <strong>F<\/strong><\/li><\/ul><\/li><li>ordenar <strong>F <\/strong>en orden ascendente<\/li><li>siempre que la cola no est\u00e9 vac\u00eda<ul><li>Desplazarse <strong>F<\/strong> -&gt; borde <strong>Para<\/strong><\/li><li>si la adici\u00f3n de <strong>Para <\/strong>no crea un ciclo en G &#039;luego agrega <strong>Para<\/strong> En g &#039;<\/li><\/ul><\/li><li>volver G &#039;<\/li><\/ul><\/div><p style=\"text-align: justify;\">Para saber si creamos un ciclo, basta con saber si podemos llegar a un v\u00e9rtice de la arista partiendo del otro v\u00e9rtice en G &#039;. Como recordatorio, en un \u00e1rbol solo hay un camino de un v\u00e9rtice a otro.<\/p><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"i\"><\/span>\u00a0<img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-6285 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/kruskal.png\" alt=\"cubierta de \u00e1rbol kruskal\" width=\"350\" height=\"219\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/kruskal.png 350w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/kruskal-300x188.png 300w\" sizes=\"(max-width: 350px) 100vw, 350px\" \/><span class=\"ez-toc-section-end\"><\/span><\/h2><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Algorithme-de-Prim\"><\/span>Algoritmo de Prim<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">El principio es agrandar un \u00e1rbol agregando un borde de peso m\u00ednimo incidente al \u00e1rbol.<\/p><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p>Al principio, el gr\u00e1fico G &#039;contiene solo un v\u00e9rtice de G:<\/p><ul style=\"text-align: justify;\"><li>siempre que G &#039;no contenga todos los v\u00e9rtices de G<ul><li>poner en fila todas las aristas de G que conectan un v\u00e9rtice de G &#039;a un v\u00e9rtice que no est\u00e1 en G&#039;<\/li><li>ordenar en orden ascendente la cola<\/li><li>siempre que la cola no est\u00e9 vac\u00eda o se haya agregado un borde<ul><li>desplazarse por la cola -&gt; borde <strong>Para<\/strong><\/li><li>si la adici\u00f3n de <strong>Para <\/strong>no crea un ciclo en G &#039;luego agrega <strong>Para<\/strong> En g &#039;<\/li><\/ul><\/li><\/ul><\/li><\/ul><\/div><p style=\"text-align: justify;\">Siendo complejo el algoritmo de entender por escrito, mostraremos un ejemplo:<\/p><p style=\"text-align: justify;\"><img decoding=\"async\" class=\"aligncenter wp-image-2678 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/prim.png\" alt=\"cubierta de \u00e1rbol primitiva\" width=\"273\" height=\"269\" title=\"\"><\/p><h2><span class=\"ez-toc-section\" id=\"Kruskal-pas-a-pas\"><\/span>Kruskal paso a paso<span class=\"ez-toc-section-end\"><\/span><\/h2><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6459 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal1.png\" alt=\"cubierta de \u00e1rbol kruskal\" width=\"441\" height=\"356\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal1.png 441w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal1-300x242.png 300w\" sizes=\"(max-width: 441px) 100vw, 441px\" \/><\/p><p>A continuaci\u00f3n se muestra la lista de bordes ordenados por peso:<\/p><table><tbody><tr><td width=\"61\">Espina de pescado<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">antes de Cristo<\/td><td width=\"56\">EF<\/td><td width=\"56\">CF<\/td><td width=\"56\">AF<\/td><td width=\"56\">BF<\/td><td width=\"53\">FD<\/td><\/tr><tr><td width=\"61\">Peso<\/td><td width=\"56\">2<\/td><td width=\"56\">3<\/td><td width=\"56\">4<\/td><td width=\"56\">4<\/td><td width=\"56\">5<\/td><td width=\"56\">5<\/td><td width=\"56\">6<\/td><td width=\"56\">7<\/td><td width=\"56\">8<\/td><td width=\"53\">8<\/td><\/tr><\/tbody><\/table><p>______________<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6460 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal2.png\" alt=\"cubierta de \u00e1rbol kruskal\" width=\"318\" height=\"269\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal2.png 318w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal2-300x254.png 300w\" sizes=\"(max-width: 318px) 100vw, 318px\" \/><\/p><p>Ning\u00fan ciclo detectado<\/p><table><tbody><tr><td width=\"61\">Espina de pescado<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">antes de Cristo<\/td><td width=\"56\">EF<\/td><td width=\"56\">CF<\/td><td width=\"56\">AF<\/td><td width=\"56\">BF<\/td><td width=\"53\">FD<\/td><\/tr><tr><td width=\"61\">Peso<\/td><td width=\"56\">2<\/td><td width=\"56\">3<\/td><td width=\"56\">4<\/td><td width=\"56\">4<\/td><td width=\"56\">5<\/td><td width=\"56\">5<\/td><td width=\"56\">6<\/td><td width=\"56\">7<\/td><td width=\"56\">8<\/td><td width=\"53\">8<\/td><\/tr><\/tbody><\/table><p>______________<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6461 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal3.png\" alt=\"cubierta de \u00e1rbol kruskal\" width=\"330\" height=\"265\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal3.png 330w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal3-300x241.png 300w\" sizes=\"(max-width: 330px) 100vw, 330px\" \/><\/p><p>Ning\u00fan ciclo detectado<\/p><table><tbody><tr><td width=\"61\">Espina de pescado<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">antes de Cristo<\/td><td width=\"56\">EF<\/td><td width=\"56\">CF<\/td><td width=\"56\">AF<\/td><td width=\"56\">BF<\/td><td width=\"53\">FD<\/td><\/tr><tr><td width=\"61\">Peso<\/td><td width=\"56\">2<\/td><td width=\"56\">3<\/td><td width=\"56\">4<\/td><td width=\"56\">4<\/td><td width=\"56\">5<\/td><td width=\"56\">5<\/td><td width=\"56\">6<\/td><td width=\"56\">7<\/td><td width=\"56\">8<\/td><td width=\"53\">8<\/td><\/tr><\/tbody><\/table><p>______________<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6462 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal4.png\" alt=\"cubierta de \u00e1rbol kruskal\" width=\"270\" height=\"241\" title=\"\"><\/p><p>Ning\u00fan ciclo detectado<\/p><table><tbody><tr><td width=\"61\">Espina de pescado<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">antes de Cristo<\/td><td width=\"56\">EF<\/td><td width=\"56\">CF<\/td><td width=\"56\">AF<\/td><td width=\"56\">BF<\/td><td width=\"53\">FD<\/td><\/tr><tr><td width=\"61\">Peso<\/td><td width=\"56\">2<\/td><td width=\"56\">3<\/td><td width=\"56\">4<\/td><td width=\"56\">4<\/td><td width=\"56\">5<\/td><td width=\"56\">5<\/td><td width=\"56\">6<\/td><td width=\"56\">7<\/td><td width=\"56\">8<\/td><td width=\"53\">8<\/td><\/tr><\/tbody><\/table><p>______________<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6463 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal5.png\" alt=\"cubierta de \u00e1rbol kruskal\" width=\"362\" height=\"284\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal5.png 362w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal5-300x235.png 300w\" sizes=\"(max-width: 362px) 100vw, 362px\" \/><\/p><p>Ning\u00fan ciclo detectado<\/p><table><tbody><tr><td width=\"61\">Espina de pescado<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">antes de Cristo<\/td><td width=\"56\">EF<\/td><td width=\"56\">CF<\/td><td width=\"56\">AF<\/td><td width=\"56\">BF<\/td><td width=\"53\">FD<\/td><\/tr><tr><td width=\"61\">Peso<\/td><td width=\"56\">2<\/td><td width=\"56\">3<\/td><td width=\"56\">4<\/td><td width=\"56\">4<\/td><td width=\"56\">5<\/td><td width=\"56\">5<\/td><td width=\"56\">6<\/td><td width=\"56\">7<\/td><td width=\"56\">8<\/td><td width=\"53\">8<\/td><\/tr><\/tbody><\/table><p>______________<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6464 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal6.png\" alt=\"cubierta de \u00e1rbol kruskal\" width=\"310\" height=\"246\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal6.png 310w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/kruskal6-300x238.png 300w\" sizes=\"(max-width: 310px) 100vw, 310px\" \/><\/p><table><tbody><tr><td width=\"61\">Espina de pescado<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">antes de Cristo<\/td><td width=\"56\">EF<\/td><td width=\"56\">CF<\/td><td width=\"56\">AF<\/td><td width=\"56\">BF<\/td><td width=\"53\">FD<\/td><\/tr><tr><td width=\"61\">Peso<\/td><td width=\"56\">2<\/td><td width=\"56\">3<\/td><td width=\"56\">4<\/td><td width=\"56\">4<\/td><td width=\"56\">5<\/td><td width=\"56\">5<\/td><td width=\"56\">6<\/td><td width=\"56\">7<\/td><td width=\"56\">8<\/td><td width=\"53\">8<\/td><\/tr><\/tbody><\/table><ul><li>Ciclo detectado: no usar BC<\/li><\/ul><p>Ning\u00fan ciclo detectado, n-1 flanco-&gt; FIN<\/p><table><tbody><tr><td width=\"61\">Espina de pescado<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">antes de Cristo<\/td><td width=\"56\">EF<\/td><td width=\"56\">CF<\/td><td width=\"56\">AF<\/td><td width=\"56\">BF<\/td><td width=\"53\">FD<\/td><\/tr><tr><td width=\"61\">Peso<\/td><td width=\"56\">2<\/td><td width=\"56\">3<\/td><td width=\"56\">4<\/td><td width=\"56\">4<\/td><td width=\"56\">5<\/td><td width=\"56\">5<\/td><td width=\"56\">6<\/td><td width=\"56\">7<\/td><td width=\"56\">8<\/td><td width=\"53\">8<\/td><\/tr><\/tbody><\/table><h2><span class=\"ez-toc-section\" id=\"Prim-pas-a-pas\"><\/span>Prim paso a paso<span class=\"ez-toc-section-end\"><\/span><\/h2><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6465 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim1.png\" alt=\"cubierta de \u00e1rbol primitiva\" width=\"605\" height=\"618\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim1.png 605w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim1-294x300.png 294w\" sizes=\"(max-width: 605px) 100vw, 605px\" \/><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-6466 size-full alignnone\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim2.png\" alt=\"cubierta de \u00e1rbol primitiva\" width=\"605\" height=\"215\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim2.png 605w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim2-300x107.png 300w\" sizes=\"(max-width: 605px) 100vw, 605px\" \/><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6467 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim3.png\" alt=\"cubierta de \u00e1rbol primitiva\" width=\"605\" height=\"210\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim3.png 605w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim3-300x104.png 300w\" sizes=\"(max-width: 605px) 100vw, 605px\" \/><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6468 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim4.png\" alt=\"cubierta de \u00e1rbol primitiva\" width=\"604\" height=\"193\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim4.png 604w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim4-300x96.png 300w\" sizes=\"(max-width: 604px) 100vw, 604px\" \/><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6469 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim5.png\" alt=\"cubierta de \u00e1rbol primitiva\" width=\"805\" height=\"272\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim5.png 805w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim5-300x101.png 300w\" sizes=\"(max-width: 805px) 100vw, 805px\" \/><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6470 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/prim6.png\" alt=\"cubierta de \u00e1rbol primitiva\" width=\"597\" height=\"211\" 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<\/div>","protected":false},"excerpt":{"rendered":"<p>Teor\u00eda de grafos P\u00e1gina de inicio Wiki \u00c1rboles de expansi\u00f3n Se dice que un subgrafo de G se expande si contiene todos los v\u00e9rtices de G. Un subgrafo de expansi\u00f3n no es \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-2621","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2621","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=2621"}],"version-history":[{"count":19,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2621\/revisions"}],"predecessor-version":[{"id":18425,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2621\/revisions\/18425"}],"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=2621"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}