Final Remarks

We covered two algorithms for finding minimum spanning trees in connected graphs. Finding a minimum spanning tree can be used in the context of telecommunication networks. However, like the other concepts discussed in this course, the concept of a minimum spanning tree can also be applied in novel ways. One instance of such an application is this approximation algorithm for the metric traveling salesperson problem.

In the context of minimum spanning trees, we looked at a specific use case of the disjoint-set data structure, where each disjoint set represents a connected component. In other situations, a disjoint-set data structure can represent connected parts of a grid or network. For instance, it can store information about a social network. In such a case, the data structure can be used for assessing whether some information can be transmitted from one individual to another based on whether they are in the same connected component.

We covered the Ford-Fulkerson algorithm and saw how it can be used for finding a maximum flow of material in a flow network such as a network of water supply, distribution of goods, or electrical transmission. We saw that the Ford-Fulkerson algorithm can also be used for finding a minimum cut in a flow network, making it useful for solving problems like identifying traffic congestions.

Note that the Ford-Fulkerson algorithm is an excellent starting point for an introduction to problems related to flows. It’s considered a landmark algorithm that has had a tremendous impact on how real-world combinatorial optimization problems are tackled.

An interesting application of the Ford-Fulkerson algorithm is image segmentation, where we are required to identify what part of an image constitutes its foreground and what part constitutes its background. In such a case, the pixels are modeled as vertices, and each pair of adjacent pixels is modeled as an edge. Once the algorithm is run, the vertices that fall in the two sets $V_s$ and $V_t$ of the minimum cut $\langle V_s, V_t\rangle$ correspond to the foreground and background of the image.

We also saw how the Ford-Fulkerson algorithm can be used as a subroutine for finding maximum matchings and minimum vertex covers in bipartite graphs.

Many applications that require pairing objects, animals, or people belonging to two different groups can be framed as the problem of finding a maximum matching in a bipartite graph. For example, one such application is in computer vision, where different objects moving through an environment are required to be tracked across different video frames. In such a case, two consecutive video frames are treated as partite sets, and the objects in each frame are treated as vertices.