Least weight set of arcs connecting all vertices

Concept of a Least Weight Set of Arcs Connecting all Vertices

  • Known as the minimum spanning tree (MST), this represents the set of arcs that connects all vertices in a graph without any cycles and with the least total weight.
  • Real-world applications of this concept include network design like telecommunications, power grid, and piping systems where it’s essential to connect all nodes at the minimum cost.
  • The weight of the spanning tree is represented by the sum of weights of all the arcs in the tree.

Algorithms for Finding the Minimum Spanning Tree

  • Kruskal’s Algorithm and Prim’s Algorithm are the two main algorithms used frequently to solve the minimum spanning tree problem.
  • Both these algorithms make use of greedy technique where the next best or local optimum move is chosen at each step with an aim to find the global optimum solution.

Kruskal’s Algorithm

  • This algorithm works by sorting all the edges from the lowest weight to the highest.
  • Then it crosses each edge off the list in order, and adds it to the spanning tree, as long as the edge does not create a cycle.
  • The algorithm was named after its discoverer, Joseph Kruskal, a mathematician and a computer scientist.

Prim’s Algorithm

  • Prim’s algorithm works by starting with a single vertex and continuously adding the smallest edge that connects the growing tree to a vertex not yet in the tree.
  • Conceived by Robert C. Prim in 1957, it’s a way to find a minimum spanning tree in a weighted undirected graph.

Common Pitfalls and Errors

  • Beware of disconnected graphs. Both algorithms fail to give a minimum spanning tree for a graph that is not connected.
  • Distinguishing between visited and unvisited vertices is crucial as it saves time and prevents cycles.

Practical Application and Exercises

  • Real-life scenarios such as planning roads between towns or laying down cables can aid in understanding the concept of a minimum spanning tree.
  • Doing coding exercises implementing Kruskal’s Algorithm and Prim’s Algorithm can consolidate the learner’s understanding.
  • Using contrasting examples to visualise the sequences of the process for both algorithms supports cognitive understanding.