Cover trees - Complex systems and AI

Contents

Covering trees

A subgraph of G is said to cover if it contains all the vertices of G.

A spanning subgraph is not necessarily connected. A tree covering of G is a covering subgraph of G, and this subgraph is a tree.

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.

This is referred to as a minimum weight spanning tree. This problem is a network creation problem: either 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
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 '
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 '

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