Hello, and welcome back. My name is William and today I'm going to talk about common problems in graph theory. A lot of problems you will encounter can often be reduced to a famous or well known problem or some variant thereof. So it's important to be able to familiarize ourselves with common graph theory problems and their solutions. Just before getting started falling off from what we learned in the last video about representing graphs, I want you to think about how you would store and represent the graphs in the upcoming problems I'm going to describe, in particular, is the graph and the problem I'm describing directed or undirected, are the edges of the graph weighted or unweighted is the common use case a graph that is likely to be sparse or dense with edges and lastly, should I use it adjacency matrix and adjacency list, an edge list or some other structure to represent my graph efficiently.

So one of the most, if not the most common problem in graph theory is the shortest path problem. Given a weighted graph, find the shortest path of edges from node A to node B. So, if we pretend this graph represents a road system, and we're at node A and want to get to note H, our shortest path algorithm should be able to find us a list of edges to follow that will lead us from A to h with a minimal cost. Lucky for us many algorithms exist to solve the shortest path problem, including a breadth first search for unweighted graphs, the extras algorithm Bellman Ford, a star and many more. As simple as it sounds, connectivity is a big issue in graph theory. The problem can also be simplified to does there exist a path from node A to node B in this scenario, we don't care about the minimum costs, we just want to know, can one node reach another node?

A typical solution to this problem is to use a union find a structure, or do a very basic search algorithm such as a depth first search or a breadth first search. Another common problem is detecting negative cycles in a directed graph. Sometimes we're dealing with graphs that have negative edge weights. And we need to know if a negative cycle exists, because if there does, it can throw everything off. In this graph nodes One, two and three form a negative cycle. Because if you cycle through all the nodes, you end up with a cost of negative one if you add up all the edge weights, in fact, you can cycle endlessly getting Smaller and Smaller costs.

In the context of finding the shortest path a negative cycle is like a trap that you can never escape. However, there are some contexts where negative cycles are beneficial. Suppose we're trading currencies across an exchange or multiple exchanges. Currency prices try to remain consistent throughout the day across exchanges, such as trading USD to euros or Canadian to yen. But sometimes there are inconsistencies in the currency exchange prices. This makes it possible to do something called an arbitrage, which cycles through multiple currencies exchanging one currency for another and coming back to the original currency with more money than you originally started at a risk free game.

This is something we can use graph theory for because it uses detecting negative cycles. There are two well known algorithms that can detect negative cycles and those are Bellman Ford and Floyd warshall. Some thing that comes up now and again is finding strongly connected components within a graph. This is analogous to finding connected components of an undirected graph. But for directed graphs, when looking at strongly connected components, we're looking for self contained cycles within the graph where every vertex in a given cycle should be able to reach every other vertex in that same cycle. This is very useful in many algorithms, and is usually an intermediate step.

So it's important to know how to find these strongly connected components. And there are many very elegant algorithms to do so such as Tarzan's algorithm. You probably won't go through your computer science career without hearing about the traveling salesperson problem. The tsp problem is the problem of having n cities and the distances Between each of them, and finding the shortest path that visits each city and comes back to the original city at minimum cost. For example, if your graph is the one on the left, a possible tsp solution is the graph on the right, which has a cost of nine. The tsp problem is NP hard, meaning it is computationally challenging problem.

This is unfortunate because the TSP problem has several very important applications. Some famous algorithms we can use to actually solve this problem are the healed Karp algorithm with dynamic programming doing some kind of branching and bounding algorithm, or you can use one of many, many approximation algorithms such as the ant colony optimization. This next problem I want to talk about is finding bridges in the graph, which is something of a fascination to me, bridges our edges which if removed, increases The number of connected components in a graph. And this graph the edges highlighted in pink are bridges. bridges are important in graph theory because they often hint at weak points, bottlenecks or vulnerabilities in a graph. Think of your graph as a telephone network or a set of bridges between islands, you can immediately see the usefulness of detecting bridges related to bridges, but not the same articulation points, which are nodes that if removed, increase the number of connected components in the graph.

In this same graph, you can see the three articulation points highlighted in pink. Next problem is finding the minimum spanning tree of a graph. A minimum spanning tree is a subset of the edges that connects all the vertices together without any cycles and with minimal possible cost. So in summary, it's a tree meaning it has no cycles and It spans the graph at a minimal cost, hence why we give it the name minimum spanning tree. For example, in the graph below. One of the possible minimum spanning trees is this graph with a least cost of 12.

Note that all minimum spanning trees of a graph have the same minimal cost, but are not necessarily identical. minimum spanning trees are seen in lots of different applications in computer science, including designing a least cost network circuit design transportation networks, you name it. There's also several approximation algorithms which rely on minimum spanning trees which is pretty interesting. If you want to find a minimum spanning tree of a graph, I recommend using one of Kuru schools prims or both cuz algorithm. This last problem I think, is the most fascinating and it is about finding the maximum flow through a special type of graph called In a flow network flow networks are networks where edge weights represent capacities in some sense, capacities might be things like the maximum amount of cars that fit on a road, or the maximum amount of volume that can flow through a pipe, or even the number of boats a river can sustain without destroying the environment.

And these types of flow networks we often find ourselves asking the question with an infinite input source, that is cars, water boats, whatever, how much flow? Can I push through the network? Assuming we start at some source and try and make it to some sync node? This question is important because at some point, there is bound to be a bottleneck somewhere in our flow graph that limits the amount of stuff we can have traveling on the network, making it from point A to point B maximum flow would then represent things like the volume of water allowed to flow through the network of pipes, the number of cards the roads can sustain and traffic or the maximum amount of boats allowed on the river. With these maximum flow problems, we can identify the bottlenecks that slow down the whole network and fix the edges that have lower capacities.

That's all the problems I want to talk about today. If I missed the problem, please feel free to list it in the description below. Thanks for watching, and I think in the next video, I'll be covering the depth first search algorithm so stay tuned and subscribe for more mathematics and computer science videos.