Graph Theory Basics: Fresh Take

Lumen Learning

Graph Theory Basics: Fresh Take

Recognize graph components: vertices, edges, loops, and vertex degrees
Identify both a path and a circuit through a graph
Determine whether a graph is connected or disconnected
Find the shortest path through a graph using Dijkstra’s Algorithm

Drawing Graphs

The Main Idea

In the world of Graph Theory, we’re not talking about bar graphs or pie charts. Instead, we’re diving into a network of dots and lines, known as vertices and edges, that help us solve real-world problems like finding the shortest path in a network. Here, you’ll learn about the essential components of a graph, such as vertices, edges, loops, and vertex degrees. You’ll also get to know about paths, circuits, and the concept of connected and disconnected graphs. Plus, we’ll introduce you to the idea of ‘weights’ on edges, which can represent various factors like distance or cost.

Vertex: Think of it as a meeting point or a junction. In a city map, it could be an intersection.
Edge: This is the line connecting two vertices. Imagine it as a road linking two intersections.
Loop: A special edge that starts and ends at the same vertex. Picture a roundabout at an intersection.
Degree of a Vertex: Count the number of edges meeting at a vertex. It’s like counting the number of roads that intersect at a junction.
Path: A sequence of vertices where you don’t repeat any vertex. It’s like going from point [latex]A[/latex] to [latex]B[/latex] without revisiting any place.
Circuit: A path that starts and ends at the same vertex. Imagine a circular route that brings you back to where you started.
Connected Graphs: If you can travel from any vertex to any other vertex, the graph is connected. Think of it as a well-planned city where you can get from any place to another without being stuck.
Weights: These are special numbers assigned to edges. They can represent distances, costs, or any other metric that matters in your problem.

Back in the 18th century in the Prussian city of Königsberg, a river ran through the city and seven bridges crossed the forks of the river. The river and the bridges are highlighted in the picture below.^[1]

A map of the city of Königsberg, with the 7 bridges crossing the river highlighted

As a weekend amusement, the townsfolk would see if they could find a route that would take them across every bridge once and return them to where they started.

In the following video we present another view of the Königsberg bridge problem.

You can view the transcript for “Drawing a graph for bridges” here (opens in new window).

Leonard Euler (pronounced OY-lur), one of the most prolific mathematicians ever, looked at this problem in 1735, laying the foundation for graph theory as a field in mathematics. To analyze this problem, Euler introduced edges representing the bridges:

A simplified map with four ovals, labeled North Bank, East Bank, South Bank, and Island, respectively. North Bank and South Bank each have two connections to Island and one to East Bank. Island has two connections to North Bank, two connections to South Bank, and one connection to East Bank. East Bank has one connection to North Bank, one to Island, and one to South Bank.

Since the size of each land mass, it is not relevant to the question of bridge crossings, each can be shrunk down to a vertex representing the location:

An even further simplified map with four dots, labeled NB, EB, SB, and I, respectively. NB and SB each have two connections to I and one to EB. I has two connections to NB, two connections to SB, and one connection to EB. EB has one connection to NB, one to I, and one to SB.

Notice that in this graph there are two edges connecting the north bank and island, corresponding to the two bridges in the original drawing. Depending upon the interpretation of edges and vertices appropriate to a scenario, it is entirely possible and reasonable to have more than one edge connecting two vertices.

While we haven’t answered the actual question yet of whether or not there is a route that crosses every bridge once and returns to the starting location, the graph provides the foundation for exploring this question.

Watch the following video for more information on graph theory basics. Note: Ignore the assignment at the end of the video

You can view the transcript for “Basic Concepts in Graph Theory” here (opens in new window).

Shortest Path

The Main Idea

Ever wondered how Google Maps finds the quickest route for you? It’s not magic; it’s Graph Theory in action! This section dives deeper into the concept of finding the shortest path in a graph using algorithms, specifically Dijkstra’s Algorithm. Algorithms are your step-by-step guides to solving complex problems. Dijkstra’s Algorithm not only finds the shortest path but does so efficiently, saving both time and computational resources.

Shortest Path: It’s not always about the distance; sometimes it’s about time or even cost. Always consider the ‘weights’ on the edges.
Dijkstra’s Algorithm: This is your go-to for finding the shortest path. It starts with marking the end vertex and works its way back, calculating distances.
Steps to find the shortest path between two vertices using the Dijkstra’s Algorithm:
1. Mark the ending vertex with a distance of zero. Designate this vertex as current.
2. Find all vertices leading to the current vertex. Calculate their distances to the end. Since we already know the distance the current vertex is from the end, this will just require adding the most recent edge. Don’t record this distance if it is longer than a previously recorded distance.
3. Mark the current vertex as visited. We will never look at this vertex again.
4. Mark the vertex with the smallest distance as current, and repeat from step [latex]2[/latex].
Efficiency: In the world of algorithms, efficiency is key. Dijkstra’s Algorithm is both optimal and efficient, making it a popular choice for many applications.
Calculations: The number of calculations needed for Dijkstra’s Algorithm is around [latex]V^2[/latex], where [latex]V[/latex] is the number of vertices. Efficient, isn’t it?

A shipping company needs to route a package from Washington, D.C. to San Diego, CA. To minimize costs, the package will first be sent to their processing center in Baltimore, MD then sent as part of mass shipments between their various processing centers, ending up in their processing center in Bakersfield, CA. From there it will be delivered in a small truck to San Diego.The travel times, in hours, between their processing centers are shown in the table below. Three hours has been added to each travel time for processing. Find the shortest path from Baltimore to Bakersfield.

	Baltimore	Denver	Dallas	Chicago	Atlanta	Bakersfield
Baltimore	*			[latex]15[/latex]	[latex]14[/latex]
Denver		*		[latex]18[/latex]	[latex]24[/latex]	[latex]19[/latex]
Dallas			*	[latex]18[/latex]	[latex]15[/latex]	[latex]25[/latex]
Chicago	[latex]15[/latex]	[latex]18[/latex]	[latex]18[/latex]	*	[latex]14[/latex]
Atlanta	[latex]14[/latex]	[latex]24[/latex]	[latex]15[/latex]	[latex]14[/latex]	*
Bakersfield		[latex]19[/latex]	[latex]25[/latex]			*

While we could draw a graph, we can also work directly from the table.

Step [latex]1[/latex]: The ending vertex, Bakersfield, is marked as current.
Step [latex]2[/latex]: All cities connected to Bakersfield, in this case Denver and Dallas, have their distances calculated; we’ll mark those distances in the column headers.
Step [latex]3[/latex] & [latex]4[/latex]: Mark Bakersfield as visited.

Here, we are doing it by shading the corresponding row and column of the table. We mark Denver as current, shown in bold, since it is the vertex with the shortest distance.

	Baltimore	Denver [latex][19][/latex]	Dallas [latex][25][/latex]	Chicago	Atlanta	Bakersfield [latex][0][/latex]
Baltimore	*			[latex]15[/latex]	[latex]14[/latex]
Denver		*		[latex]18[/latex]	[latex]24[/latex]	[latex]19[/latex]
Dallas			*	[latex]18[/latex]	[latex]15[/latex]	[latex]25[/latex]
Chicago	[latex]15[/latex]	[latex]18[/latex]	[latex]18[/latex]	*	[latex]14[/latex]
Atlanta	[latex]14[/latex]	[latex]24[/latex]	[latex]15[/latex]	[latex]14[/latex]	*
Bakersfield		[latex]19[/latex]	[latex]25[/latex]			*

Step [latex]2[/latex] (#[latex]2[/latex]): For cities connected to Denver, calculate distance to the end. For example, Chicago is [latex]18[/latex] hours from Denver, and Denver is [latex]19[/latex] hours from the end, the distance for Chicago to the end is [latex]18+19 = 37[/latex] (Chicago to Denver to Bakersfield). Atlanta is [latex]24[/latex] hours from Denver, so the distance to the end is [latex]24+19 = 43[/latex] (Atlanta to Denver to Bakersfield).

Step [latex]3[/latex] & [latex]4[/latex] (#[latex]2[/latex]): We mark Denver as visited and mark Dallas as current.

	Baltimore	Denver [latex][19][/latex]	Dallas [latex][25][/latex]	Chicago [latex][37][/latex]	Atlanta [latex][43][/latex]	Bakersfield [latex][0][/latex]
Baltimore	*			[latex]15[/latex]	[latex]14[/latex]
Denver		*		[latex]18[/latex]	[latex]24[/latex]	[latex]19[/latex]
Dallas			*	[latex]18[/latex]	[latex]15[/latex]	[latex]25[/latex]
Chicago	[latex]15[/latex]	[latex]18[/latex]	[latex]18[/latex]	*	[latex]14[/latex]
Atlanta	[latex]14[/latex]	[latex]24[/latex]	[latex]15[/latex]	[latex]14[/latex]	*
Bakersfield		[latex]19[/latex]	[latex]25[/latex]			*

Step [latex]2[/latex] (#[latex]3[/latex]): For cities connected to Dallas, calculate the distance to the end. For Chicago, the distance from Chicago to Dallas is [latex]18[/latex] and from Dallas to the end is [latex]25[/latex], so the distance from Chicago to the end through Dallas would be [latex]18+25 = 43[/latex]. Since this is longer than the currently marked distance for Chicago, we do not replace it. For Atlanta, we calculate [latex]15+25 = 40[/latex]. Since this is shorter than the currently marked distance for Atlanta, we replace the existing distance.

Step [latex]3[/latex] & [latex]4[/latex] (#[latex]3[/latex]): We mark Dallas as visited, and mark Chicago as current.

	Baltimore	Denver [latex][19][/latex]	Dallas [latex][25][/latex]	Chicago [latex][37][/latex]	Atlanta [latex][40][/latex]	Bakersfield [latex][0][/latex]
Baltimore	*			[latex]15[/latex]	[latex]14[/latex]
Denver		*		[latex]18[/latex]	[latex]24[/latex]	[latex]19[/latex]
Dallas			*	[latex]18[/latex]	[latex]15[/latex]	[latex]25[/latex]
Chicago	[latex]15[/latex]	[latex]18[/latex]	[latex]18[/latex]	*	[latex]14[/latex]
Atlanta	[latex]14[/latex]	[latex]24[/latex]	[latex]15[/latex]	[latex]14[/latex]	*
Bakersfield		[latex]19[/latex]	[latex]25[/latex]			*

Step [latex]2[/latex] (#[latex]4[/latex]): Baltimore and Atlanta are the only non-visited cities connected to Chicago. For Baltimore, we calculate [latex]15+37 = 52[/latex] and mark that distance. For Atlanta, we calculate [latex]14+37 = 51[/latex]. Since this is longer than the existing distance of [latex]40[/latex] for Atlanta, we do not replace that distance.

Step [latex]3[/latex] & [latex]4[/latex] (#[latex]4)[/latex]): Mark Chicago as visited and Atlanta as current.

	Baltimore [latex][52][/latex]	Denver [latex][19][/latex]	Dallas [latex][25][/latex]	Chicago [latex][37][/latex]	Atlanta [latex][40][/latex]	Bakersfield [latex][0][/latex]
Baltimore	*			[latex]15[/latex]	[latex]14[/latex]
Denver		*		[latex]18[/latex]	[latex]24[/latex]	[latex]19[/latex]
Dallas			*	[latex]18[/latex]	[latex]15[/latex]	[latex]25[/latex]
Chicago	[latex]15[/latex]	[latex]18[/latex]	[latex]18[/latex]	*	[latex]14[/latex]
Atlanta	[latex]14[/latex]	[latex]24[/latex]	[latex]15[/latex]	[latex]14[/latex]	*
Bakersfield		[latex]19[/latex]	[latex]25[/latex]			*

Step [latex]2[/latex] (#[latex]5[/latex]): The distance from Atlanta to Baltimore is [latex]14[/latex]. Adding that to the distance already calculated for Atlanta gives a total distance of [latex]14+40 = 54[/latex] hours from Baltimore to Bakersfield through Atlanta. Since this is larger than the currently calculated distance, we do not replace the distance for Baltimore.

Step [latex]3[/latex] & [latex]4[/latex] (#[latex]5[/latex]): We mark Atlanta as visited. All cities have been visited and we are done.

The shortest route from Baltimore to Bakersfield will take [latex]52[/latex] hours, and will route through Chicago and Denver.

You can view the transcript for “Graph Theory: Dijkstra’s Algorithm” here (opens in new window).

For more information on Dijkstra’s Algorithm, watch the following video.

You can view the transcript for “Dijkstra’s Algorithm – Computerphile” here (opens in new window).

If you are curious what an algorithm is, the following video goes into algorithms in more detail.

You can view the transcript for “What’s an algorithm? – David J. Malan” here (opens in new window).

Bogdan Giuşcă. http://en.wikipedia.org/wiki/File:Konigsberg_bridges.png ↵