Nodes, Edges, and Connectivity

Algorithmically Speaking - #3: A visual introduction to the basic concepts of graph theory.

Hello there!

Today we will be diving into one of the most common ways of representing data and modeling problems (and solutions) in Computer Science. We will be talking about Graphs.

This will be the first of a series of posts introducing graph theory in a very visual way.

It will consist of some basic definitions of graph theory that will lay the basis for us to be able to explore more complex topics in future posts. The idea is to present the definitions along with visual representations, to help in the process of learning new concepts.

At the end of the post, you will find some algorithmic challenges so you can try and apply some of the topics that I will explain today. Feel free to skip to that part if you think you already have the necessary skills to solve them.

Let’s begin!

---

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 visually display them using the most simple drawings of circles and lines.

For example, here’s a hand-drawn image of a graph with 5 nodes and 7 edges that we will use to help us understand some basic definitions:

Visual representation of a graph with 5 nodes and 7 edges.

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 (red) path between the two green nodes in the following image is of length 3:

An example of a path in a graph. The green nodes represent both ends of the path. Red edges are the edges present in the path.

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 node is 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 image corresponds to a simple path, while the one in the following image is considered a cycle:

An example of a cycle in a graph. Every green node can be the starting and ending point of the cycle.

Connectivity

A graph is connected if there is a path between any two nodes. For example, our initial graph is connected: