Graphs: basic terminology

Previously, we learned some basics about graphs and considered several cases where they come in handy. You might remember the example on social networks that we looked at. Now, you probably know that Facebook is a social network that allows users to connect with friends online. Instagram is a similar platform, but users follow other users without having to add them as friends. Well, instead of spending your precious time on these networks, let's learn more about the way they work from the inside.

In this topic, we will continue with graphs and talk about some basic terminology using the graph above as an illustration. Although learning terms might seem a bit tedious, it is a very important step. Once you get familiar with the basic terms, you will be able to understand more sophisticated algorithms and concepts concerning graphs.

Simple graphs

Up until now, we talked about small graphs with plain structure. However, some graphs look a bit tricky, as shown in the picture below. There are two things to note. First: the edge $\{0, 0\}$ connects the node $0$ with itself. Such an edge is called a loop. Also, there are three edges connecting the same pair of nodes: $0$ and $1$. These are known as multiple edges. If a graph contains loops or some edges appear multiple times, it is called a multigraph. Otherwise, we call it a simple graph.

It is worth noticing that simple graphs are very common, but they are not enough. Have you ever mentioned somebody in a story on Instagram? In that case, an edge is automatically created to indicate that some interaction between users has happened. This is when they receive the message "@bob mentioned you in their story". What if you are sharing a memory from your own archive? The interaction happens between you and you; hence, it creates a loop.

Similarly, representing multiple edges is more than necessary. Let's stick to social networks. If your accounts are connected, and you follow the same person on Instagram, Facebook, and other apps, multiple edges will be used to store the information, just like in the example above with the blue, magenta, and green edges.

Nodes and edges' relationship

We already know what the graphs in Facebook's databases look like: nodes representing users that are connected by an edge with other users if and only if they are friends. Now, how do these terms and phenomena sound in the language of graphs? Let's find out.

Two nodes of a graph are adjacent if they are connected by an edge. For example, the nodes $0$ and $1$ in the graph above are adjacent, since they are connected by the edge $\{0, 1\}$. Basically, this indicates that Bob and Ann are friends. If an edge $\{x, y\}$ connects the nodes $x$ and $y$, these nodes are incident to this edge. For example, the node $1$ is incident to three edges: $\{0, 1\}$, $\{1, 3\}$, and $\{1, 2\}$. The degree of a node is the number of edges incident to it. For instance, the degree of the node $2$ is equal to $3$, since the node is incident to three edges. This means that Alice has 3 friends on Facebook, which is not much, to be honest.

Relationships in directed graphs

What if you prefer Instagram, instead? It is possible to follow someone even if they don't follow you back. In this case, directed graphs come in handy, as we need to store information about the follower and the user who is followed using directed edges.

In a nutshell, their adjacency is not symmetric: if $y$ is adjacent to $x$, $x$ is not necessarily adjacent to $y$. For example, in the graph above, node $0$ is adjacent to node $1$ since there is a directed edge from node $0$ to node $1$ i.e. $0$ $\to$ $1$. Basically, this indicates that Bob follows Ann. In directed graphs, each node has an indegree – the number of followers, in this case, and an outdegree – the number of users they follow. Formally, for a node $x$, the indegree is the number of nodes adjacent to $x$, and the number of outgoing edges of $x$ is called the outdegree. As an illustration, the indegree of node $2$ is $3$, and its outdegree is $1$. In other words, Alice has three followers and follows one user, namely Ann.

Summary

In this topic, we've considered the basic terminology used with graphs. Here is a quick recap:

• A multigraph is a graph containing multiple edges or edges connecting a node to itself, called loops. Otherwise, the graph is simple.

• Two nodes connected by an edge are called adjacent. They are said to be incident to this edge. The degree of a node is the number of edges incident to it.

• Analogously for the directed graphs, we have indegree – the number of incoming edges, and outdegree – the number of outgoing edges.

There are some more concepts related to graphs you need to learn, before you are ready to move on with graph algorithms. So, be patient till the next lesson.