2.5. Building a Minimum Cost Spanning Tree

Having seen a variety of algorithms for shortest paths on weighted graphs, we now move to a completely different problem that of computing, what is called Minimum Cost Spanning Tree.

This chunk sets up the transition from shortest path algorithms to the concept of Minimum Cost Spanning Trees (MCST). The key idea here is understanding a new type of graph problem where we want to create a tree that is not only connected but also has the minimum possible cost associated with it. A spanning tree includes all vertices of a graph connected by edges without any cycles, and an MCST minimizes the sum of the edge weights in the spanning tree.

Imagine a city that needs to build a network of roads to connect all neighborhoods while minimizing the cost of construction. Each road has a different construction cost associated with it, and the city planners want to find the best way to connect all neighborhoods without creating any dead ends or unnecessary loops, just like in the MCST problem.

Suppose, we are in a district which has a road network and after a bad cyclone, the roads are all been damaged. So, the first priority of the government is to restore the roads, so that relief can be sent to various parts of the district and also people can start moving around again.

Here, the text provides a real-world scenario where the concept of MCST becomes crucial. After a disaster like a cyclone, the government needs to prioritize which roads to restore in order to ensure connectivity among the affected areas. Restoring roads efficiently would involve selecting a set of roads that connect all essential points with minimal resources, echoing the principles behind Minimum Cost Spanning Trees.

Think about how if a town experienced a flood, the local authorities would prioritize which roads to repair first based on their importance and the cost involved. By choosing the cheapest set of roads that ensures everyone can move freely, they are effectively applying the idea of an MCST.

So, what we want is a connected sub graph of this original graph which does not have any loops which is acyclic and this is precisely what is called a tree. So, tree by definition is a connected acyclic graph.

This chunk defines what a tree is in the context of graph theory. A tree is defined to be a connected acyclic graph, meaning it connects all its nodes (or vertices) without forming any loops. For an MCST, we are looking for such a tree that not only maintains this property but also minimizes the total cost associated with its edges.

Consider a family tree, which connects all family members. It's structured in a way that no individual member is repeated (acyclic) and it shows connections to each relative without any loops, just like how an MCST connects different points in a cost-effective manner.

In this graph for instance, one spanning tree we could form, other red edges shown here, 1 to 2, 2 to 3, 3 to 4 and 4 to 5. Of course, we could form other spanning trees...

In this chunk, the text illustrates an example of constructing spanning trees within a graph. It emphasizes that multiple spanning trees can exist for a given graph, demonstrating the different connections (or edges) that can link all vertices while obeying the acyclic condition.

Imagine you have multiple routes to get from one neighborhood to another. Just like different spanning trees, you can take various paths to ensure each part of the neighborhood is connected. Each path might represent a different way of restoring the road system after the cyclone.

Now, suppose that the graph also has weights. In this example, the weight for instance, could be the cost of repairing a road.

This chunk introduces the concept of weights in the context of spanning trees. Here, the focus is on the costs associated with each edge (or road). The goal is not just to form a spanning tree, but to do so in a way that minimizes the total cost of the selected edges. By comparing different trees, one can determine which configuration yields the least expense.

If you think of planning a community event, the costs of setting up different booths (like roads) might vary. You'd want to organize your event in such a way that covers all necessary areas while spending as little as possible.

By definition, a tree is a connected acyclic graph. The claim is that any tree has exactly n minus 1 edges.

This section discusses a fundamental property of trees which states that if a tree has 'n' vertices, it will have exactly 'n-1' edges. This is a crucial characteristic because it lays the foundation for understanding how spanned connections work, confirming there's a balance between the number of vertices and edges in a tree.

Picture a simple family tree with five family members. There can only be four connections (edges) between them. If you add another connection, you start going in circles, thus making it not a simple family tree anymore—mirroring how trees in graph theory function.

If I take a tree and then I add an edge, it must create a cycle...

In this part, the text explains how adding edges to a tree affects its structure. If you were to add an edge to a tree, a cycle would inevitably form, violating the tree's acyclic property. This is essential in ensuring that any adjustments to a tree still respect its defining characteristics.

Think of a bicycle chain that connects each link in a specific sequence. If you try to connect a new link in a way that forms a loop with existing links, it disrupts the chain's function and makes it less efficient—just as adding an edge disrupts the acyclic nature of a tree.

Between any two vertices in a tree, there can only be one unique path.

This highlights another property of trees: there is a unique path connecting any two vertices. If there were multiple paths, it would imply that a cycle exists, contradicting what it means to be a tree. This attribute is vital for understanding how trees function in connecting nodes in a straightforward manner.

Imagine you are trying to navigate through an underground maze. If there's only one route leading from one exit (vertex) to another, you will not get lost. If there were two routes, you'd likely end up wandering in circles, just as trees cannot allow for such redundancies.

So, our target right now is to build a minimum cost spanning tree. So, there are two naturally greedy strategies that one can think of...

Here, the text introduces two greedy algorithms to find an MCST: Prim's Algorithm and Kruskal's Algorithm. Prim's algorithm begins with the smallest weight edge and incrementally adds edges while keeping the tree connected. Kruskal's Algorithm, on the other hand, examines edges in ascending order and adds them to the forest of trees unless it forms a cycle, eventually connecting all components into a tree.

Consider a shopping scenario: when buying groceries, you might first pick the cheapest items each time (like Prim's) or you might lay out all the items and choose the cheapest one that doesn't already fill your basket (like Kruskal's). Both methods help you maximize your savings while still fulfilling your needs.

--