2. Minimum Cost Spanning Trees

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.

To motivate the problem, let us consider the following example. Suppose, we are in a district which has a road network and after a bad cyclone, the roads are all being 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. So, the priority is to restore enough roads, so that everybody can move around. So, the first criteria for the government to restore road is to ensure connectivity. So, given this which set of roads should the government restore first?

This chunk introduces the concept of Minimum Cost Spanning Trees (MCST) using a practical example of a cyclone damage scenario. The focus here is on the necessity to restore connectivity in a disrupted road network. The government must prioritize which roads to restore first to ensure that all areas of the district can be accessed. This sets the groundwork for understanding that the goal of an MCST is not merely to restore all roads, but to do so in a way that minimizes redundancy and cost.

Think of a network of water pipes where after a storm, some pipes are damaged. The city needs to fix the pipes but wants to spend as little money as possible. By focusing on fixing just enough pipes to keep the water flowing everywhere without creating any unnecessary loops, the city can effectively manage its budget while ensuring everybody gets water again.

If the main criterion is minimum connectivity, then it should be clear that there is no point in restoring roads which find a loop. For instance, supposing we restore all these four roads, then we could have deleted any one of these roads, say 3 to 4 or 2 to 3 and still one can get from any of these four towns to any four other towns in the district. So, removing an edge from a loop cannot disconnect a graph and our aim is to find some subset of edges within this graph which are connected in such a way that this is a minimal such set of edges.

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 part clarifies that in order to maintain minimum connectivity while restoring roads, it is unnecessary to restore roads that create loops. Removing edges that are part of a loop does not affect overall connectivity. Hence, the focus should be on identifying a subset of roads (edges) that maintain connectivity without forming cycles. This leads to the definition of a tree: a connected acyclic graph, which effectively models the desired structure for connectivity without redundancy.

Imagine a family tree. Each person is connected (like edges) to their parents or children. If every family member has only one parent-child connection (no loops) it ensures clarity. If someone had multiple parents listed, it would create confusion similar to having loops in a graph. A family tree helps visualize relationships simply, much like how a tree structure helps maintain a road network.

In particular, we start to the arbitrary graph and we are looking for a tree which sits inside the graph, which is a sub-graph in terms of the number of the edges, which connects all the vertices in the original graph. So, such a tree is called a spanning tree, it spans the vertices of the original graph, but it forms a tree outer the subset of three edges.

This chunk describes the concept of a 'spanning tree'. A spanning tree is defined as a tree that covers all the vertices of the original graph while being acyclic and connected. In essence, it is a way to connect all points (vertices) in the graph with the minimum number of connections (edges). The specific requirement is that it should minimize the overall connections while ensuring no cycles are formed, which directly leads us to the concept of minimum spanning trees.

Think of a bus route that needs to pass through several neighborhoods. The goal is to connect all neighborhoods with as few stops as possible without any one stop serving as a redundant loop. The bus route acts like a spanning tree, covering all necessary stops without unnecessary detours, similar to how a spanning tree connects graph vertices efficiently.

Now, suppose that the graph also has weights. In this example, the weight for instance could be the cost of repairing a road. So, supposing restoring the road has a cost and now the government would like to not only restore connectivity, but do it at minimum cost. So, if for instance, the government chose to repair this tree of roads, then the total cost is 18 plus 6, 24 plus 70, 94 plus 20, 114. So, it could incur cost of 114 to the store, this spanning tree. On the other hand, if the government chooses green spanning tree, then the cost reduces to 10 plus 6 is 16 plus 20 is 36 plus 8 is 44.

In this chunk, the discussion shifts to graphs with weights. Here, weights represent costs, such as the expense of repairing a specific road. The example outlines two different spanning trees with corresponding costs, illustrating how the choice of edges affects the total repair cost. The goal is to determine the spanning tree with the minimum cost, which in this case is illustrated with the green spanning tree costing 44 instead of 114.

Consider planning a road trip where each route has different toll costs. You want to find the cheapest route to visit all your destinations without going back and forth unnecessarily. By calculating which routes incur the least tolls, you create a plan that resembles finding a minimum cost spanning tree for the road routes.

Before we move ahead to algorithms to compute minimum cost spanning trees, let us look at some basic facts about trees. So, remember that by definition, a tree is a connected acyclic graph. So, the graph in general will have n vertices, so the claim is that any tree has exactly n minus 1 edges.

This segment establishes foundational properties of trees. It reiterates that a tree is characterized as a connected, acyclic graph, and notably points out that any tree with 'n' vertices must contain exactly 'n-1' edges. This is an essential concept for understanding the structure of trees in graphs, as it emphasizes the relationship between vertices and edges, providing a basis for further exploration of algorithms for finding minimum cost spanning trees.

Imagine a classroom of 10 students where every student needs to connect with every other student to share ideas. To achieve this, each student can form a unique link with 9 others which results in exactly 9 connections. This scenario reflects the principle that a connected structure (tree) will have edges equal to one less than the nodes (students).

Another consequence of all these definitions is that between any two paths, any two vertices in a tree, there can only be one unique path. So, supposing there are actually two paths, so let us look at two vertices, here we have drawn them as i and j and suppose there are two parts. So, if I follow the two parts, then it is very clear that because there are two different ways are going there, there will be some loops somewhere in between. So, notice that it need not to be a loop including i and j, it could be somewhere in between i and j.

This portion highlights an important property of trees: there exists exactly one unique path between any two vertices in a tree. It emphasizes that if multiple paths were found, it would imply the presence of a loop, contradicting the acyclic nature of trees. This characteristic aids in understanding how information or connectivity flows through a tree structure, which is crucial when analyzing and constructing spanning trees.

Think of a subway system where each station is a vertex and the tracks are edges. If you need to travel from station A to station B, there is one direct train route (path) with no alternate routes. If there were multiple train tracks linking stations A and B, it would create confusion about which to take, just like multiple paths create loops in a tree structure.

--