Posts Tagged ‘spanning tree’

Problem 1079

Use Kruskal’s Algorithm to find the minimum spanning tree for the weighted graph. Give the total weight of the minimum spanning tree.

D5

Solution:-

 

Step 1. Find the edge with the smallest weight.

Select edge AB (weight: 72)

 

Step. Find the next-smallest edge in the graph.

Select edge CD (weight : 77).

 

Step 3. Find the next-smallest edge in the graph that does not create a circuit.

Select edge AC (weight: 81).

 

There three edges create a subgraph that contains all of the graph’s four vertices, is connected, and contains no circuits. Furthermore, since the edges with the smallest weights were chosen, the resulting spanning tree should be the minimum spanning tree for the weighted graph.

The following tree matches the shape of the minimum spanning tree.

D6

From the figure, we see that the total weight of the minimum spanning tree is

72 + 77 +81 = 230

 

Problem 1078

Find a spanning tree for the connected graph.

D3

Solution:-

 

Given a graph, a sub graph is a set vertices and edges chosen from those of the original graph. A graph can have many subgraphs. A subgraph that contains all of a connected graph’s vertices, is connected, and contain no circuits is called a spanning tree. A graph can have many spanning trees.

The original graph is a connected graph with 6 vertices and 8 edges.

The spanning tree of a graph with n vertices has n – 1 edges.

 

Therefore , the spanning tree of the original graph must have 6 – 1 = 5 edges. Since the original graph has 8 edges, 3 edges will need to be removed to create the spanning tree.

 

Remove three edges to create one possible spanning tree, as shown to the right. Notice that each edge is a bridge and no circuits are present.

D4