2.2. 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.

So, 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?

In this chunk, we introduce the concept of Minimum Cost Spanning Trees (MCST). It starts by contextualizing the problem within real-life scenarios, such as restoring roads after a disaster. The emphasis is on ensuring connectivity among various parts of a district through a road network. The key takeaway is that to solve the problem effectively, the government needs to determine which roads to repair first, ensuring that all towns remain connected while minimizing costs.

Imagine a city that suffers from a flood, with many roads underwater. The city's management must decide which roads to repair first to allow emergency services to reach all neighborhoods quickly. This scenario illustrates the importance of connectivity and cost-effectiveness in infrastructural decision-making.

So, 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 sub set 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.

This chunk explains the characteristics of trees in graph theory, particularly focusing on the acyclic nature of trees. It states that any loops in a graph are unnecessary when aiming for connectivity since they do not contribute to the overall minimum spanning condition. Therefore, the goal is to identify a subset of edges that keeps the graph connected without forming loops, leading to the definition of a 'tree,' which is a connected and acyclic graph.

Think of a bicycle wheel. The spokes connect to the center without forming any loops. Just like the spokes ensure the wheel's structure is strong and functional, the edges in a tree connect vertices without any unnecessary paths, ensuring that all points are reached efficiently without redundancy.

So, tree by definition is a connected acyclic graph. And 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 sub set of three edges.

This section clearly defines 'spanning trees' as specific types of trees that include all vertices of a given graph but with the minimum number of edges needed to maintain connectivity. A spanning tree exists as a subgraph of the original graph and fulfills the criteria of being a tree: it connects all vertices without forming loops.

Consider a small community with several houses (vertices) connected by a few main roads (edges). A spanning tree represents one way to connect all houses with the fewest roads necessary, allowing all residents to visit each other without taking unnecessary detours that would create loops.

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 I mean 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 is16 plus 20 is 36 plus 8 is 44. So, different spanning trees now will come at different cost and the goal would be to reduce the cost per minimum.

In this part, we highlight the concept of weights in a graph, translating to costs associated with maintaining or restoring edges (roads). The government’s challenge is not only to restore connectivity but to do it while minimizing costs. By evaluating different spanning trees based on their repair costs, it becomes evident that some configurations are more financially efficient than others, significantly affecting decision-making priorities.

Imagine a homeowner trying to fix a series of leaks in their roof. Each type of repair has a different cost. Just like the government seeking to minimize costs when fixing roads, the homeowner must choose which leaks to repair first, aiming to use the least amount of money while covering all areas that need attention.

So, 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 chunk emphasizes the foundational properties of trees, particularly focusing on their structure. It claims that every tree with n vertices must have exactly n - 1 edges, a property that is pivotal for understanding how trees function within graphs. This property helps in establishing the relationships between vertices and ensures that the graph maintains its tree characteristics.

Think of a small team of people (vertices) connected through a network of relationships (edges). If every person must be connected without any duplications or extra connections, the number of relationships must be exactly one less than the number of people, ensuring that everyone is connected with the fewest dealings possible—just like a tree.

Now, if I take a tree and then I add an edge, it must create a cycle, we already saw this in this previous argument that we said, so supposing I have a tree, so a tree in general looks something like this. So, it is a graph, it has a kind of more cycles, but many things branching out. Now, if anywhere if I create a tree, supposing I add them and supposing I take some i there and some j here, we may decide to add an edge. So, we know that because it is a tree, there is already connection. So, there is some path which in this case to this vertex from i to j. So, therefore, that path p plus this edge forms acyclic.

This section explains that adding an edge to an existing tree will inevitably lead to the formation of a cycle. Since trees are acyclic, any new edge that connects two vertices already connected by existing paths must create at least one loop. This property is crucial in understanding why trees cannot contain any redundancies in their structure.

Imagine a tree being like a cable that connects different sections of a high-tension power line. If you try to connect another cable in such a way that it loops back to an existing section, you create a problem — it may cause interference (a cycle) with the original flow of electricity. This illustrates why adding edges to a tree must be done with care to avoid cycles.

So, 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.

This chunk highlights that in a tree, for any two vertices (points) there exists a unique path that connects them. If there were multiple paths, it would imply a loop, which contradicts the definition of a tree. This concept of uniqueness is fundamental to the structure and function of trees in graph theory.

Think of a family tree as a diagram. If each person in the family is represented as a node, there’s only one direct lineage (path) leading to each family member; it avoids confusion and ensures clarity that each person has a distinct line of descent without any loops back to earlier generations.

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. One is, since you are looking for a minimum cost tree to start with this smallest stage and incrementally build the tree. So, we keep adding edges to the existing tree, so that the new graph remains a tree and it grows as little as possible in terms of cost. This will give raise to an algorithm which is called prim’s algorithm. It will also turn out to be very similar to Dijkstra’s shortest path algorithm with a single source.

In this chunk, we introduce the concept of constructing a Minimum Cost Spanning Tree using two primary strategies: building incrementally from the smallest edges or considering edges in rising order while maintaining the tree properties. Prim's algorithm is highlighted as a method of growing a tree stepwise, ensuring cost-effective connections without cycles. This lays the groundwork for further exploration of how these algorithms operate.

Imagine crafting a mosaic where each tile comes with a cost. You want to cover the entire surface efficiently. Just as you would begin with the cheapest tiles and lay them carefully to avoid overlaps, creating a minimum cost spanning tree involves selecting edges (roads) wisely to minimize overall expenditure while fully connecting a network.

--