Spanning tree

A subgraph of G is a spanning graph if it has all G’s vertices.
A spanning subgraph is not necessarily connected. A spanning tree of G is a spanning subgraph of G, and this subgraph is a tree.

arbre9

It is easy to build a spanning tree:

  • as long as we do not add n-1 edges to G’, with n the number of vertices of the graph, we choose an edge of G so that its addition does not create a cycle in G’.
  • as long as the number of remaining edges is greater than n-1, an edge of G is removed so that G is always connected.

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

This is called a minimal spanning tree. This problem is: there are n vertices to connect, we know the costs to connect one vertex to another, we try to connect all places at the lowest cost.

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

Kruskal

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

  • for each vertex v of G
    • add v to f
  • order f esc
  • while the queue is not empty
    • unstack f -> edge a
    • if a does not create a cycle in graph G’ then  a in G’
  • return G’

To know if one creates a cycle, it is enough to know if one 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

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

At first, the graph G’ contains only one vertex of G:

  • while G’ has not all the vertices of G
    • stack in a queue all the edge of G which connects a vertex of G’ to one not in G’
    • order esc the queue
    • while the queue is non-empty or one has added an edge
      • unstack queue -> edge a
      • if  a does not create a cycle in G’ then add a in G’

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

prim

 

Publicités