Question

Consider the following graph.

(a) What is the cost of its minimum spanning tree?

(b) How many minimum spanning trees does it have?

(c) Suppose Kruskal’s algorithm is run on this graph. In what order are the edges added to the MST? For each edge in this sequence, give a cut that justifies its addition.

Short answer

a).The cost of its minimum spanning treeby usingKruskal’s algorithm is 19.

b).Theminimum number of spanning trees does is 2.

c). Theorder of the edges added to the MST or each edge in the sequence is$AE,EF,BE,FG,GH,CG,andGD$.

Step-by-step solution

A minimal spanning tree:

A minimal spanning tree is indeed an edge-weighted graph with a weight that is equal to which is less than the value about any other spanning tree.

The least cost of spanning tree.  

a)

Minimum spanning tree cost:

The number of edges for a minimal spanning tree may be calculated using the formula below.:

$\mathrm{Number}\mathrm{of}\mathrm{edges}=\mathrm{Number}\mathrm{of}\mathrm{vertices}–1$

In Equation, replace$"\mathrm{number}\mathrm{of}\mathrm{vertices}=8"$with the value.

$$\begin{gathered} \mathrm{Number}\mathrm{of}\mathrm{edges}=8–1 \\ =7 \end{gathered}$$

The following are the steps to determining the least spanning tree:

Begin with the graph's vertices " A ."

• Each vertices "A " has two angles with such a load of 6 vertices point A to point B and 1 vertices from to .

• From A through E vertices, the minimum weight is 1 as indicated below:

Next, starts with vertex “B ”.

• The vertex "B " has four edges with weights of 6 vertices from B to A ,5 vertices from B to C ,2 vertices from B to E , and 2 vertices from B to F . From B to E vertices, the minimum weights are 2; from B to F vertices, the minimum weights are 2. Take a look at the initial minimal weight value. As a result, the minimal weight 2 from B to E vertices are as follows:

Then comes the vertex " C ."

• Each vertices " C " has four edges having weights of 5 vertices through C to B ,6 vertices as C to D,5 vertices from C to F, and 4 vertices from C to G.

• From C through G vertices, the lower limit is 4 as indicated below:

Then comes the vertex "D ."

• Each vertices "D" has four edges having weights of 5 vertices through D to B,6 vertices as D to D ,5 vertices from D to F, and 4 vertices from D to G.

• From D through G vertices, the lower limit is 4.

Then comes the vertex " E ."

• The vertex "E " has three edges with weights of one from E to A , two from E to B, and one from E to F vertices.

• The first and second weights have already been drawn.

From E through F vertices, the minimum weight is 1 as indicated below:

Next, begin with vertex "F ."

• The vertex "F " has four edges, each with a weight of one from F to E , two from F to B , five between F and C , and three from F to G .

• The first and second weights have already been drawn.

From F through G vertices, the minimum weight is 3 as indicated below:

The following vertex is "$G$."

• The vertex "G" has four edges with weights of 3 between G and F vertices,4 between G and C vertices,5 between G and D vertices, and 3 between G and H vertices.

• The third and fourth weights have already been drawn.

o From G through H vertices, the minimum weight is 3 as illustrated below:

Finally, the minimum spanning tree is shown below:

The cost of the minimum spanning tree is the sum of all the weighted edges.

Therefore, the cost of the minimum spanning tree: 19

The number of minimum spanning tree in this graph.

b)

In the given graph, there are two possibilities of the minimum spanning tree. That is, we can take the weight 2 from B to E or weight 2 fromEtoF .

One possible minimum spanning tree with weight$2fromBtoE$and is given below:

Another possible minimum spanning tree with weight$2fromEtoF$and is given below:

Therefore, the number of minimum spanning tree in this graph is 2.

Run the MST using Kruskal’s algorithm:

c)

The minimum spanning tree using the Kruskal’s algorithm is given below:

In this MST,

• There are 7 edges are included into the minimum spanning tree such as,

$AE,EF,BE,FG,GH,CG,andGD.$

$$\begin{gathered} •For\mathrm{AE}edge,thecutsare\left\{A,B,C,D\right\}and\left\{E,F,G,H\right\}. \\ •ForEFedge,thecutsare\left\{A,B,C,D,E\right\}and\left\{F,G,H\right\}. \\ •ForBEedge,thecutsare\left\{A,E,F,G,H\right\}and\left\{B,C,D\right\}. \\ •ForFGedge,thecutsare\left\{A,B,E\right\}and\left\{C,D,F,G,H\right\}. \\ •ForGHedge,thecutsare\left\{A,B,E,F,G\right\}and\left\{C,D,H\right\}. \\ •ForCGedge,thecutsare\left\{A,B,E,F,G,H\right\}and\left\{C,D\right\}. \\ •ForGDedge,thecutsare\left\{A,B,C,E,F,G,H\right\}and\left\{D\right\}. \end{gathered}$$