1 sollins algorithm

Graph ,MST , SOLLINS ALGORITHM

1. Soling's Algorithm Department of Electrical Engineering GC University, Lahore Engr .Salman 0306-4111558

2. Contents Graph Basic term associate with Graph Spanning Tree Condition for spanning tree Spanning Tree properties Minimum–cost spanning Tree Application of MST Algorithms for Minimum-cost-spanning tree Sollin’s Algorithm

3. Graph Non-Linear data structure A graph G is finite set of vertices and edges G(E,V). Graph is used to represent many real life application.like Models for electrical wiring Social network like facebook , linkedln . GPS (Global position system)[1] Application of graph

4. Terms associate with graph Vertex Edge Directed and un-directed graph A-cyclic graph Edge Weight Example of Un-directed graph Directed a-cyclic graph

5. Spanning Trees (ST) For undirected and connected graph G ,spanning tree T is the subset of G which contain all vertices and does not have a cycle.[2] Example Connected un-directed graph Remove edges w hich are producing cycle. Spanning Tree

6. Conditions For Spanning tree A graph should be connected A disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices. A graph should have at least more than than three vertices

7. Properties of Spanning Tree  F or complete undirected graph Maximum number of spanning tree=    n n-2 Spanning tree does not have a cycle. Spanning trees have same number of vertices as graph G. All possible spanning tree have same number of vertices and edges. Spanning tree has n-1 edges. If we add an edge to a spanning tree it creat a cycle.

8. Minimum-cost spanning trees (MST) The cost of a spanning tree would be the sum of the costs of its edges A minimum-cost spanning tree is a spanning tree that has the lowest cost A minimum cost spanning tree is used to find the shortest path. Example / Spanning tree MST Total cost=1+2+3+4+5=15 Total cost=2+4+5=11 Total cost=1+2+4=7

9. Conitnue … If all the edges have unit cost then all spanning tree are minimal cost spanning tree and have same cost. Because all the spanning tree have dame number of vertices and edges.

10. Application of MST Minimum spanning trees have direct applications in the design of  networks , .for example computer networks telecommunications networks transportation networks water supply networks electrical grids[3]

11. Minimax Process 2 2 -3 7 2 8 -3 R B

12. Taxonomy

13. Algorithms to find MST Kruskal’s algorithm Prim’s algorithm Sollin’s algorithm

14. Sollin’s Algorithm Sollin’s algorithm is also called Boruvka’s algorithm It is used to find MST. It was given by Boruvkas in 1926.at tthat time it was the first algorithm to find the MST. Boruvka’s Algorithm is a  greedy algorithm  and is similar to  Kruskal’s algorithm  and  Prim’s algorithm . [4]

15. Greedy Algorithm Algorithm are designed to solve the problem. In greedy algorithm ,first off all we check all the possibilities of a given problem, then at the first stage we select that which can give optimal solution . At the next stage always choose the  next piece that offers the most benefit. Greedy algorithm is an algorithm that builds up a solution piece by piece.

16. Steps of Sollin’s Algorithm Write all vertices of a connected graph. Highlight the cheapest outgoing edge of all vertices. Choose only one cheapest edge for each vertex. Repeat the algorithm for each sub graph (each differently colored set). This time, for each node, choose the cheapest edge  outside of the sub-graph. If an edge is already selected then skip it. 5 1 6 4 3 2 10 28 14 16 12 18 22 25 24 Connected graph 5 1 6 4 3 2 10 14 12 22 25 16 MST

17. Example Undirected graph Cost =87

18. Conti… MST Cost=62

19. References [1] www.uow.edu.au /~ bmaloney/wuct121/GraphsWeek11Lecture2.pdf [2]-https :// www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm [ 3]-https://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm [4]-Fundamental of data structure by in c++ by Sartaj //ch#6 pp#361

20. ANY QUESTION ??