Heuristics: Minimal Spanning Tree 1

A Minimum-Cost Spanning Tree is a weighted, undirected, connected subgraph with minimal total costs.

Theory

Spanning Trees

We are given a connected graph with undirected edges in order to reach every node from any other. A prerequisite is that the graph has to contain all vertices of our search space.

To get a spanning tree we have to find a subgraph connecting all nodes with the following constraint: to provide only one simple path to get from one node to any other.

If there was more than one way to reach any node from a given starting node in the subgraph, it would contain a cycle.

A graph with v vertices will produce a spanning tree that has v-1 edges. If the graph itself has only v-1 edges it already is in strict conformity with the spanning tree and a unique solution. Otherwise several spanning trees might be set up.

Examples

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

A connected graph with undirected edges: Every node can be reached from any other and all given nodes are connected within the graph.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

This chosen subgraph is no tree as it contains a cycle in (D,C,F).

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Connecting v=6 vertices with v-1=5 edges, these are two possible spanning trees for the graph.

Minimum-Cost Spanning Trees

If we have a function that assigns a value to every edge, we can transform the graph into a weighted graph. The function could allocate transport costs or distances to the edges.

Our target operator is to minimize or maximize the function value sum of a subgraph. Assuming we are dealing with transport costs, we have to find a subgraph that minimizes our total costs.

Due to the fact that we need a minimum of v-1 edges to connect all vertices, our subgraph will be a tree. A tree, being a subgraph with a minimum of total costs, is called a Minimum-Cost Spanning Tree.

Examples

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

A graph with added costs to every edge (now: weighted edges).

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

A possible spanning tree for the graph (v-1=5 edges) with total costs of 31.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

A minimal spanning tree for the graph with total costs of 15.

Algorithms

Prim's Algorithm

A node is always connected by its cheapest outgrowing edge to the rest of the minimal spanning tree.

Within Vojtěch Jarník's algorithm we iteratively connect direct neighbors (reachable by one single edge) to our set of previously chosen nodes until all vertices are linked.

We can start from every node for the simple reason that all nodes have to be connected to the tree.

start: choose a random node
cycle: fix the cheapest edge connecting our yet chosen part of the tree to a direct neighbor (which has not been connected so far)
end: if all nodes are connected by fixed edges

This algorithm will always find an optimal solution on condition that our function assigns real numbers to all vertices.

The optimal solution is unique in case all edge costs are unequal.

Example

We now solve our initial problem for a minimal spanning tree with the Prim's Algorithm:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

We choose node A randomly. Possible neighbors to A are B,D or C. We choose the cheapest edge to B.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Direct neighbors to our previously chosen vertices are E, D or C. We add D by (B,D) to our so far created minimal spanning tree.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

We do not consider (A,D) in this step as A is already connected. Instead, we add (D,C).

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

We now add F with node costs of 5.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Finally we select E by node (F,E).

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

After deploying the Prim's Algorithm, we have a Minimum-Cost Spanning Tree with total costs of 15.

Kruskal's Algorithm

First of all we have to sort all edges by their costs. Then we iteratively add the cheapest edges that are still on the list.

As mentioned above, we must not add an edge if it creates a cycle. Instead, we can ignore this edge. We proceed until v-1 edges are added properly.

start: sort all edges by their costs
cycle: add the cheapest edge that is still available to the tree, considering it does not create a cycle with the previously added ones.
end: if v-1 edges are added

This algorithm also always finds an optimal solution on condition that our function assigns real numbers to all vertices.

The found solution is unique in case of all edge costs are unequal.

Example

The same graph as above, now solved with Kruskal's:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

We create a list of all edges and sort them by their costs.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

We begin picking the cheapest edge and put it on our set of selected connections.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Afterwards, we set the following edge (E,F).

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

We add (B,D). Since we have a count of three valid edges, we now have to check if they create a cycle.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

If there are edges with the same cost, we check them in a freely selectable manner. It reveals that (A,D) is an invalid connection because it would create the cycle (B,D,A). As mentioned above, this connection is now fully blocked.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

We add (D,C) instead and check for cycles. We have four valid edges selected so far.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

We finish our work as we found 5 valid edges.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

After the utilization of Kruskal's Algorithm, we have a Minimum-Cost Spanning Tree with total costs of 15.

Sources

http://lcm.csa.iisc.ernet.in/dsa/node181.html
http://www.mathcove.net/petersen/lessons/get-lesson?les=47
http://delphiforfun.org/programs/Math_Topics/MinimalSpanningTrees.htm
http://en.wikipedia.org/wiki/Minimum_spanning_tree
http://compprog.wordpress.com/2007/11/09/minimal-spanning-trees-prims-algorithm/
http://md-english.wikispaces.com/file/view/minimum_spanning_trees.pdf