Minimum Spanning Trees in Networks
Name\Tareq Babaqi
The cost of the spanning tree is the sum of the weights of all the
edges in the tree. There can be many spanning trees. Minimum
spanning tree is the spanning tree where the cost is minimum
among all the spanning trees. There also can be many minimum
spanning trees.
Minimum spanning tree has direct application in the design of
networks. It is used in algorithms approximating the travelling
salesman problem, multi-terminal minimum cut problem and
minimum-cost weighted perfect matching. Other practical
applications are:
Cluster Analysis
Handwriting recognition
Image segmentation
In the minimum spanning tree problem the
minimum total weighted spanning tree is
searched in a given network.
xij
: if edge (i,j) is on the minimum spanning
tree 1, otherwise 0.
Let Ck be the set of nodes that have been
covered by the minimum spanning tree up to
iteration k, and Uk be the set of remaining
nodes.
Step 1: Select any node i in set N. S
et C1= {i},U1= N-{i}, k = 2.
Step 2:
Select the node j in the set Uk-1that
yields the shortest edge to a node in This edge
is an element of the minimum spanning tree.
Set Ck=Ck-1+ {j}, and Uk=Uk-1 – {j}.
Step 3:
If Ck=N STOP, otherwise k=k+1 and
go to Step 2.
Thank You
A minimum spanning tree is a vital concept in network design, optimizing various problems like the traveling salesman issue. This text explains its importance, practical applications, and the iterative process to identify it within a network.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees. Minimum spanning tree has direct application in the design of networks. It is used in algorithms approximating the travelling salesman problem, multi-terminal minimum cut problem and minimum-cost weighted perfect matching. Other practical applications are: Cluster Analysis Handwriting recognition Image segmentation
In the minimum spanning tree problem the minimum total weighted spanning tree is searched in a given network. xij : if edge (i,j) is on the minimum spanning tree 1, otherwise 0.
Let Ck be the set of nodes that have been covered by the minimum spanning tree up to iteration k, and Uk be the set of remaining nodes. Step 1: Select any node i in set N. Set C1= {i}, U1= N-{i}, k = 2.
Step 2: Select the node j in the set Uk-1that yields the shortest edge to a node in This edge is an element of the minimum spanning tree. Set Ck=Ck-1+ {j}, and Uk=Uk-1 {j}. Step 3: If Ck=N STOP, otherwise k=k+1 and go to Step 2.
