{"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\/en\/graph-theory-2\/covering-trees\/","title":{"rendered":"Covering trees"},"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\/en\/graph-theory-2\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Graph theory<\/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\/en\/\">\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\">Home page<\/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\">Contents<\/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=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/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\/en\/graph-theory-2\/covering-trees\/#Arbres-couvrants\" >Covering trees<\/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\/en\/graph-theory-2\/covering-trees\/#Algorithme-de-Kruskal\" >Kruskal algorithm<\/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\/en\/graph-theory-2\/covering-trees\/#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\/en\/graph-theory-2\/covering-trees\/#Algorithme-de-Prim\" >Prim&#039;s algorithm<\/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\/en\/graph-theory-2\/covering-trees\/#Kruskal-pas-a-pas\" >Kruskal step by step<\/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\/en\/graph-theory-2\/covering-trees\/#Prim-pas-a-pas\" >Prim step by step<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Arbres-couvrants\"><\/span>Covering trees<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;\">A subgraph of G is said to cover if it contains all the vertices of 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;\">A spanning subgraph is not necessarily connected. A <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/\">tree<\/a> covering of G is a covering subgraph of G, and this subgraph is a tree.<\/div><p>In order to minimize the cost of power grids, wiring connections, piping, automatic voice recognition, etc., we use algorithms that gradually build a spanning tree (or more of these trees) as intermediate steps in the process of search for minimum covering trees.<\/p><p>The Internet and many other telecommunications networks have transmission links that connect nodes together in a mesh topology that includes some loops. In order to avoid bridge loops and routing loops, many routing protocols designed for such networks require each router to remember a spanning tree.<\/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=\"tree covering\" width=\"233\" height=\"151\" title=\"\"><\/p><p style=\"text-align: justify;\">It is easy to build a tree covering:<\/p><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><ul style=\"text-align: justify;\"><li>as long as we have not added n-1 edges to G&#039;, with n the number of vertices of the <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a>, we choose an edge of G in such a way that its addition does not create a cycle in G&#039;.<\/li><li>as long as the number of remaining edges is greater than n-1, we remove an edge from G such that G is always connected.<\/li><\/ul><\/div><p style=\"text-align: justify;\">The problem of spanning trees is widely used in the context of weighted edges.<\/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;\">This is referred to as a minimum weight spanning tree. This problem is a network creation problem: either <strong>not<\/strong> places to connect, we know the costs to connect one place to another, we are looking to connect all places at the lowest cost.<\/div><p style=\"text-align: justify;\">To make a spanning tree of minimal weight, we will state two greedy algorithms.<\/p><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Algorithme-de-Kruskal\"><\/span>Kruskal algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p>At the start, the graph G &#039;contains only the vertices of G and we have an empty queue (fifo) <strong>f <\/strong>:<\/p><ul style=\"text-align: justify;\"><li>for each vertex <strong>v<\/strong> by G<ul><li>add <strong>v<\/strong> To <strong>f<\/strong><\/li><\/ul><\/li><li>to sourt out <strong>f <\/strong>in ascending order<\/li><li>as long as the queue is not empty<ul><li>scroll <strong>f<\/strong> -&gt; edge <strong>To<\/strong><\/li><li>if the addition of <strong>To <\/strong>does not create a cycle in G &#039;then add <strong>To<\/strong> in G &#039;<\/li><\/ul><\/li><li>return G &#039;<\/li><\/ul><\/div><p style=\"text-align: justify;\">To know if we create a cycle, it suffices to know if we can reach a vertex of the edge starting from the other vertex in G &#039;. As a reminder, in a tree there is only one path from one vertex to another.<\/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=\"kruskal tree covering\" 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>Prim&#039;s algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">The principle is to enlarge a tree by adding an edge of minimum weight incident to the tree.<\/p><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p>At the beginning, the graph G &#039;contains only one vertex of G:<\/p><ul style=\"text-align: justify;\"><li>as long as G &#039;does not contain all the vertices of G<ul><li>put in a row all the edges of G which connect a vertex of G &#039;to a vertex which is not in G&#039;<\/li><li>sort in ascending order the queue<\/li><li>as long as the queue is not empty or an edge has been added<ul><li>scroll the queue -&gt; edge <strong>To<\/strong><\/li><li>if the addition of <strong>To <\/strong>does not create a cycle in G &#039;then add <strong>To<\/strong> in G &#039;<\/li><\/ul><\/li><\/ul><\/li><\/ul><\/div><p style=\"text-align: justify;\">The algorithm being complex to understand in writing, we will show an example:<\/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=\"prim tree covering\" width=\"273\" height=\"269\" title=\"\"><\/p><h2><span class=\"ez-toc-section\" id=\"Kruskal-pas-a-pas\"><\/span>Kruskal step by step<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=\"kruskal tree covering\" 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>Below is the list of edges sorted in order of weight:<\/p><table><tbody><tr><td width=\"61\">Fish bone<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">BC<\/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\">Weight<\/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=\"kruskal tree covering\" 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>No cycle detected<\/p><table><tbody><tr><td width=\"61\">Fish bone<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">BC<\/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\">Weight<\/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=\"kruskal tree covering\" 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>No cycle detected<\/p><table><tbody><tr><td width=\"61\">Fish bone<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">BC<\/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\">Weight<\/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=\"kruskal tree covering\" width=\"270\" height=\"241\" title=\"\"><\/p><p>No cycle detected<\/p><table><tbody><tr><td width=\"61\">Fish bone<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">BC<\/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\">Weight<\/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=\"kruskal tree covering\" 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>No cycle detected<\/p><table><tbody><tr><td width=\"61\">Fish bone<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">BC<\/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\">Weight<\/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=\"kruskal tree covering\" 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\">Fish bone<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">BC<\/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\">Weight<\/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>Cycle detected: do not use BC<\/li><\/ul><p>No cycle detected, n-1 edge-&gt; END<\/p><table><tbody><tr><td width=\"61\">Fish bone<\/td><td width=\"56\">ED<\/td><td width=\"56\">AB<\/td><td width=\"56\">CD<\/td><td width=\"56\">AE<\/td><td width=\"56\">BC<\/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\">Weight<\/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 step by step<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=\"prim tree covering\" 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=\"prim tree covering\" 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=\"prim tree covering\" 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=\"prim tree covering\" 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=\"prim tree covering\" 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=\"prim tree covering\" 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>Graph theory Home page Wiki Spanning trees A subgraph of G is said to span if it contains all the vertices of G. A spanning subgraph is not \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\/en\/wp-json\/wp\/v2\/pages\/2621","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=2621"}],"version-history":[{"count":19,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2621\/revisions"}],"predecessor-version":[{"id":18425,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2621\/revisions\/18425"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2204"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=2621"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}