Question

Draw the undirected graph X with the incident matrix of

110100

101000

011010

000011

000101

Where the edge that corresponds to edge 1 has the weight 1, and the column 2 edge represents weight 2 and so on.

b) Determine the minimum spanning tree using take away edges algorithm and with Kruskals algorithm.

Answer 1

Let us start with some basic Definition and Algorithm to clear you about what we are going to do .

Incidence Matriix:

An incidence matrix is a matrix that shows the relationship between two classes of objects.These two classes are Edge class and Vertices Classes .

If there is an edge between the any two vertices then matrix[row of vertex][column of edge] get filled with one .

Take Away Edges Algorithm :

1) Sort all edges of graph in non-increasing order of
   edge weights.

2) Initialize MST as original graph and remove extra
   edges using step 3.

3) Pick highest weight edge from remaining edges and 
   check if deleting the edge disconnects the graph  
   or not.
       If disconnects, then we don't delete the edge.
       Else we delete the edge and continue. 

Krushkal Algorithm :

1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

See the attach file for solution :