Problems in Graph Theory

William Fiset
A free video tutorial from William Fiset
Google engineer; ACM-ICPC world finalist
4.6 instructor rating • 2 courses • 106,785 students

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 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 Graff's, I want you to think about how you would store and represent the graph's 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 and adjacency list and edge lists 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 where at Node A and want to get to know each our shortest path algorithm should be able to find us a list of edges to follow that will lead us from 8H with a minimal cost. Lucky for us, many algorithms exist to solve the surest path problem, including a breathless search for unweighted graphs, Dijkstra's algorithm, Bellmon for a star and many more. As simple as that sounds, connectivity is a big issue and graph theory. The problem can also be simplified to does. There exists a path from Node eight, 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 a structure or do a very basic search algorithm, such as a death for search or a breath for a search. Another common problem is detecting negative cycles in a directed graph. Sometimes we're dealing with graphs that have negative educates and we need to know if a negative cycle exists, because if there does, it can throw everything off in this graph knows 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 educates, 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 context 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 Belmond Ford and Floyd Warshel. 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 Tarzans algorithm. You probably won't go through your computer science career without hearing about the traveling salesperson problem. The TSB problem is the problem of having and cities and the distances between each of them and finding the surest 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 TSB solution is the graph on the right, which has a cost of nine. The TSB 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 yield. Karpe 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, outer edges, which, if removed, increase the number of connected components in the graph. And this graph that I just highlighted in pink are bridges. Bridges are important and graph theory because they often hint at weak points, bottlenecks or vulnerabilities in the 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 spending tree of a graph, a minimum spang 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 sparing trees is this graph with a least cost of twelve. Note that all minimum spang trees have a graph, have the same minimal cost, but are not necessarily identical. Minimum spang trees are seen in lots of different applications in computer science, including designing a least cost network, circuit design and transportation networks, you name it. There's also several approximation algorithms which rely on minimum spacing trees, which is pretty interesting. If you want to find a minimum spang tree of a graph, I recommend using one of Crucibles Prem's or verrucas 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 edgeways represent capacities. In some sense, capacities maybe 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 as 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. The 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 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.