The Competitive Programmer's Introduction to Graph Theory
Nodes, edges, neighbors, and degrees
Hey! It’s Tivadar.
If you are a frequent reader, you have already met Alberto, the latest member of The Palindrome team. Although he primarily focuses on community building and growth, he is also a brilliant software engineer with a background in competitive programming.
I learn a lot from his insights, no matter the topic: marketing, machine learning, coding, and so on.
This is his introductory series on graph theory, from a competitive programmer’s perspective. In this first episode, we'll clear up the fundamental concepts and prepare for the adventures to come:
the art and science of graph representations,
how git uses graphs to track and analyze dependencies,
how to always find our way in any labyrinth,
and so on. Enjoy!
Cheers,
Tivadar
Nodes, Edges, and Paths
A graph consists of nodes and edges. We could see the nodes as the fundamental entities of graphs, and edges represent the relationships between nodes.
One good thing about graphs is that, even if they represent an abstract mathematical definition, we can visualize them with dots and lines.
For example, here’s an illustration of a graph with 5 nodes and 7 edges that we will use to help us understand some basic definitions:
A path leads from node a to node b through the edges of the graph. The length of a path is the number of edges in it.
For example, the highlighted path between a and b in the following figure is of length 3:
Note: The highlighted path is just one of the possible paths between the two green nodes. Try to identify every possible path between them!
A path is a cycle if the first and last nodes are the same. On the other hand, a path is called simple if each node appears at most once in the path.
For example, the highlighted path in the previous example corresponds to a simple path, while the one in the following is considered a cycle:
📌 The Palindrome breaks down advanced math and machine learning concepts with visuals that make everything click.
Join the premium tier to get access to the upcoming live courses on Neural Networks from Scratch and Mathematics of Machine Learning.
Connectivity
A graph is connected if there is a path between any two nodes. For example, our usual example graph is connected:
Try it yourself: take any pair of nodes in the previous graph and check that, indeed, there is a path between them.
On the other hand, the following graph is not connected because there is no path between the blue and the yellow nodes:
The sets of connected nodes in a graph are called connected components. Here are the connected components (nodes with the same color) of the previous graph:
We can see that this graph has two connected components.
A tree is a connected graph that consists of n nodes and n − 1 edges. There is a unique path between any two nodes of a tree. You can also think of a tree as a connected graph that doesn’t contain any cycles.
For example, the following graph is a tree:
Try it yourself: take any pair of nodes in the previous graph and check that, indeed, there is a unique path between them.
Direction and Weights
A graph is directed if the edges can be traversed in one direction only. For example, the following graph is directed:
Notice how in the following example, there is a path (more than one actually) between a and b, but not the opposite: you cannot find any path starting from b and ending at a.
As we can see, the fact that the graph is directed affects the concept of connectivity, which is called strong connectivity in the context of directed graphs. We will learn more about this in future posts of the series.
In a weighted graph, each edge is assigned a weight. The weights are often interpreted as edge lengths.
For instance, the following graph is weighted:
The length of a path in a weighted graph is the sum of the edge weights on the path. For example, in the following graph, the length of the highlighted path between the green nodes is 8 + 5 = 13:
(In future posts, we will explore algorithms related to connectivity and dig deeper into the importance of weights. Some definitions only make sense in the context of directed graphs.)
Let’s sum up what we have so far.
A graph consists of nodes and edges, where the edges represent relations between the nodes. A path is a sequence of nodes connected by edges. If the path starts and ends on the same node, it is called a cycle.
A graph is connected if there is a path between any pair of nodes. Otherwise, it is called not connected. The sets of connected nodes are called the connected components of the graph. A tree is a graph that is connected and doesn’t contain cycles.
Edges in a graph can have direction and weight. The weight of a path is the sum of the weights of the edges that belong to the path.
Neighbors and Degrees
Two nodes are neighbors or adjacent if there is an edge between them. The degree of a node is the number of its neighbors.
In the following graph, we have highlighted a node (colored in blue), its neighbors (colored in white), and the edges between them (colored in yellow):
We can see that the blue node has three incident edges and three neighbors; therefore, it has a degree of three.
In the following figure, we can see the degree of every node:
Something to notice is the fact that the sum of degrees in a graph is always 2m, where m is the number of edges. This happens because each edge increases the degree of exactly two nodes by one. So, the sum of the degrees is always even.
A graph is regular if the degree of every node is a constant d. A graph is complete if the degree of every node is n - 1, where n is the number of nodes in the graph. (That is, the graph contains all possible edges between the nodes.) By definition, a complete graph is a regular graph.
Here’s an example of a regular graph that is not complete. Notice how the degree of every node is two:
And this is an example of a complete graph. Notice how the degree of every node is three and there are four nodes:
When we are referring to directed graphs, we define the indegree of a node as the number of edges that end at the node, and the outdegree of a node as the number of edges that start at the node.
Here’s an example highlighting a node with an indegree equal to two and an outdegree equal to one:
Below are the values of indegree/outdegree for every node. Notice how some nodes can have an indegree or outdegree equal to zero:
Colorings
In a coloring of a graph, each node is assigned a color so that no adjacent nodes have the same color.
A graph is called bipartite if it is possible to find a coloring of its nodes using two colors. It can be proven that a graph is bipartite exactly when it does not contain a cycle with an odd number of edges.
For example, the following graph is bipartite. Check it out and try to find an appropriate coloring:
Here’s the coloring with two colors:
And here’s a more intuitive way to visualize bipartite graphs. The previous and the following graphs are the same:
With this representation, it becomes visually more apparent that the nodes can be split into two sets and that every edge in the graph connects nodes from different sets.
Now, let’s take a look at our usual example graph:
No matter how hard you try, you won’t be able to find a coloring of this graph using only two colors. Remember earlier, when we said that cycles of odd length and bipartiteness are related?
Inspecting the graph closely, we can notice that it contains a cycle of length 3. It won’t be possible to color this cycle (or the entire graph) using only two colors:
To recap what we have learned so far:
Two nodes are neighbors (or adjacent) if there is an edge between them. The degree of a node is the number of its neighbors.
A graph is regular if the degree of every node is constant. A graph is complete if the degree of every node is n - 1, where n is the number of nodes in the graph.
When we are referring to directed graphs, we define the indegree of a node as the number of edges that end at the node, and the outdegree of a node as the number of edges that start at the node.
A graph is called bipartite if it is possible to find a coloring of its nodes using two colors. It can be proven that a graph is bipartite exactly when it does not contain a cycle with an odd number of edges.
Test your Skills
Now that we have covered some basic definitions of graph theory, I will leave you with a couple of challenges to consider.
We can discuss the answers to these problems as a community, and you can share your answers privately by replying to this email.
Here we go:
Problem 1. Find a path with the minimum sum between the highlighted nodes on the following weighted graph.
Problem 2. What happens to the connectivity of a tree if we remove any of its edges?
Problem 3. What is the minimum number of colors needed in a valid coloring of a cycle with an odd length?
Problem 4. Is a tree a bipartite graph?
Conclusions
I hope I was able to ignite your passion for graph theory by driving you through some of the basic definitions that will allow us to build the foundations for learning more complex concepts and applications of graphs.
In the following episodes, we'll talk about
the art and science of graph representations,
how git uses graphs to track and analyze dependencies,
how to always find our way in any labyrinth,
and many more. See you soon!
Your ability to create clear illustrations to aid the learning process still amazes me to this day.
This is the perfect complement for the graph theory series!