Contenus

Toggle## Covering trees

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.

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.

It is easy to build a tree covering:

- as long as we have not added n-1 edges to G', with n the number of vertices of the graph, we choose an edge of G in such a way that its addition does not create a cycle in G'.
- 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.

The problem of spanning trees is widely used in the context of weighted edges.

**not**places to connect, we know the costs to connect one place to another, we are looking to connect all places at the lowest cost.

To make a spanning tree of minimal weight, we will state two greedy algorithms.

## Kruskal algorithm

At the start, the graph G 'contains only the vertices of G and we have an empty queue (fifo) **f **:

- for each vertex
**v**by G- add
**v**To**f**

- add
- to sourt out
**f**in ascending order - as long as the queue is not empty
- scroll
**f**-> edge**To** - if the addition of
**To**does not create a cycle in G 'then add**To**in G '

- scroll
- return G '

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 '. As a reminder, in a tree there is only one path from one vertex to another.

## Prim's algorithm

The principle is to enlarge a tree by adding an edge of minimum weight incident to the tree.

At the beginning, the graph G 'contains only one vertex of G:

- as long as G 'does not contain all the vertices of G
- put in a row all the edges of G which connect a vertex of G 'to a vertex which is not in G'
- sort in ascending order the queue
- as long as the queue is not empty or an edge has been added
- scroll the queue -> edge
**To** - if the addition of
**To**does not create a cycle in G 'then add**To**in G '

- scroll the queue -> edge

The algorithm being complex to understand in writing, we will show an example:

## Kruskal step by step

Below is the list of edges sorted in order of weight:

Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |

______________

No cycle detected

Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |

______________

No cycle detected

Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |

______________

No cycle detected

Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |

______________

No cycle detected

Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |

______________

Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |

- Cycle detected: do not use BC

No cycle detected, n-1 edge-> END

Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |