Minimum spanning tree (mst)

Minimum spanning tree (mst)

1. Minimum Spanning Tree (MST)

2. Graph In graph theory, a graph is an ordered pair G = (V, E) comprising a set of vertices or nodes together with a set of edges or arcs . Edges are 2-element subsets of V which represent a connection between two vertices. Edges can either be directed or undirected . Edges can also have a weight attribute . A Path in a network is a sequence of distinct edges that join nodes regardless of the direction of flow in each edge. A graph is connected when there is a path between every pair of vertices. A cycle is a path that starts and ends with the same vertex. A directed loop (or circuit) is a loop in which all the branches are oriented in same direction. A tree is a connected, acyclic graph. A tree is a connected network that may involve only a subset of all the nodes of the network. If a graph has n vertices, (n-1) edges and it is connected then it is a tree. A E D C B

3. A D B C Original graph A D B C A D B C A D B C A D B C A D B C (1) (2) (3) (4) (5) Graph (1), (2), (3) and (4) are spanning trees. Graph (5) consists tree but not spanning tree.

4. Original graph (1), w =24 (2), w = 18 (3), w = 22 (4), w = 20 A D B C 4 8 6 10 A D B C 8 6 10 A D B C 4 8 6 A D B C 4 8 10 A D B C 4 6 10 Graph (2) is spanning trees because it has lowest weight.

5. Spanning tree example

6. Minimum Spanning Tree example -1

7. Minimum Spanning Tree example -2

8. Applications Real-time face verification Find road networks in satellite and aerial imagery Approximation algorithms for NP-hard problems (e.g., TSP) Network design (communication, electrical, hydraulic, computer, road) Design of telecommunication networks ( fiber -optic networks, computer networks , leased-line telephone networks, cable television networks, etc .) Design of a lightly used transportation network to minimize the total cost of providing the links (rail lines, roads, etc .) Design of a network of high-voltage electrical power transmission lines Design of a network of wiring on electrical equipment (e.g., a digital computer system ) to minimize the total length of the wire Design of a network of pipelines to connect a number of locations

9. Common algorithms Prim’s Algorithm (Direct application of cut optimality theorem) Start with one (any) vertex. Branch outwards to grow your connected component. Consider only edges that leave the connected component. Add smallest considered edge to your connected component. Continue until a spanning tree is created. Kruskal’s Algorithm (Direct application of path optimality theorem) Start with |V| disjoint components. Consider lesser weight edges first to incrementally connect components. Make certain to avoid cycles. Continue until spanning tree is created.

10. Example - 0 7 1 3 2 4 6 5 6 6 5 8 8 8

11. Example - 1

12. Example - 2

13. Example - 3

14. Example - 4

15. Example - 5

16. Example - 6

17. Theorems Cut optimality theorem : Every tree arc i -j T* , ≤ for all k,l in the cut by deleting i -j from the tree . Path optimality theorem : Every non tree arc k-l , ≤ where k,l i-j T*