Problems in Graph Theory

A free video tutorial from William Fiset
Google engineer; ACM-ICPC world finalist
Rating: 4.7 out of 5Instructor rating
2 courses
113,183 students
Problems in Graph Theory

Learn more from the full course

Graph Theory Algorithms

A complete overview of graph theory algorithms in computer science and mathematics.

09:02:45 of on-demand video • Updated July 2020

Storage and representation of graphs (networks) on a computer
Common graph theory problems
Breadth first search algorithm
Depth first search algorithm
Various tree algorithms including: the height or a tree, finding the center of a tree, rooting a tree, and etc...
Dijkstra's algorithm
Topological sort algorithm
Shortest/longest path on a acyclic graph
Bellman Ford's algorithm
Floyd-Warshall all pairs shortest path algorithm
Finding bridges/articulation points
Finding strongly connected components (Tarjan's)
Travelling salesman problem (TSP)
How to find the maximum flow of a flow graph
Finding bipartite graph matchings
Various network flow algorithms including: Edmonds-Karp, Capacity Scaling, and Dinic's algorithm
Kruskal's Minimum Spanning Tree algorithm
The Lowest Common Ancestor (LCA) Problem
English [Auto]
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 a 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. Following 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 an adjacency matrix, an 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 Node 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 minimal cost. Lucky for us, many algorithms exist to solve the shortest path problem, including a breadth first search for unweighted graphs. Dijkstra's 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 to node B? In this scenario, we don't care about the minimum cost. We just want to know can one node reach another node? A typical solution to this problem is to use a union, find data 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 gain. 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. Something 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 Tarjan'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 a graph, which is something of a fascination to me. Bridges are edges which, if removed, increase 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 are 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 minimum 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 Kruskal's Prim's or Boruvka's 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 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 of 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 sink 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, The maximum flow would then represent things like the volume of water allowed to flow through the network of pipes, the number of cars the roads can sustain in 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.