Graph Basics

"...how can I link, with three, four, or at most five links of the chain, trivial, everyday things of life.

How can I link one phenomenon to another?"

Frigyes Karinthy, Chains

Introduction

How many social connections separate one person from another among Earth's entire population? If you know the concept of 'six degrees of separation', then you probably would guess six. This means you can link every human being in the world to another via a 'friend of a friend' chain in no more than six steps. Hungarian writer Frigyes Karinthy first expressed this idea in a short story in 1929. Later, in 1990, John Guare popularized it in his famous play 'Six Degrees of Separation', which was adapted into a film of the same name three years later.

What if we want to test this concept ourselves? The most intuitive way is to use the powerful notion of graphs. You find graphs in databases, social media, network providers. They play a crucial role in maintaining most of the online services we use daily. You will explore key ideas about graphs and gain a solid understanding of how they work in this lesson. Let's begin!

What is a graph?

A graph G is a pair of two sets, V and E. But what does that mean? V is the set of vertices (also known as nodes) that represent some objects. E is the set of edges that link pairs of vertices. To grasp this model, imagine vertices representing humans, and a relationship of friendship being an edge linking pairs of people who know each other. We typically draw graph nodes as circles or ellipses, and edges as lines. Look at the following example. Nodes store the names of people in a community or group, and edges represent the 'friends' relationship between them.

Three points in the above definition usually hold in Computer Science and most of its applications:

1. A graph can have several connected components. For example, envision a group of people at a cinema. Some of them are friends; some of them do not know each other at all. In this case, their social graph will be a collection of smaller connected pieces. There could also be isolated vertices that stand away from sets of connected vertices (imagine a lonely movie enjoyer). Look at the example above: It shows a connected graph consisting of one connected component. Below you can see another graph that has four connected components: two of several vertices and a couple of isolated vertices.

2. In a graph, an edge can connect one vertex with itself; such edges are called loops. In a sense, it is reasonable - I am acquainted with myself; you know yourself, etc. We will deal with graphs that do not have loops because most computer science applications see loop edges as redundant and not useful.

3. In a graph, a pair of vertices can be linked with more than one edge. Suppose your graph represents a collection of routes from one city to another. Usually, there is more than one way to drive between two destinations, given the various roads connecting the cities. However, these tasks are more complex, and we're not going to delve deeper into them at the basic level.

Therefore, an ordinary graph with vertices connected to each other via edges does not link any pair of vertices more than once. Such pairs always consist of two distinct nodes.

Types of graphs

Now that you know what a graph is, it's time to explore which properties distinguish one graph from another:

• Directed graphs: These graphs have a direction shown on their edges, turning them into arrows. By convention, if a graph has at least one edge directed, it is sufficient to consider it directed. On the other hand, an undirected graph does not have any directed edges. For example, consider a simple blueprint of a water transportation system connecting houses via pipes through which water flows. The nodes are the houses; the edges are the pipelines; and the arrows show the flow's direction. Some houses have not been connected to the water supply yet. These links are reflected as undirected edges on the graph. Despite their apparent simplicity, such models are particularly useful in many real-life engineering applications, like optimizing electricity circuits or solving transport logistics problems.

• Cyclic graphs (or simply graphs with cycles). Look at the London Tube map dating back to 1908. You can get on the underground at one station, and then, after going through various lines and stations, end up back at the same stop where you began. Many tourists experience similar confusing situations every time they visit a busy city with a sophisticated metropolitan system. In graph theory, when you see the same pattern of closed chain, it has a special name. These paths are called cycles. A graph that has at least one cycle is known as cyclic.

  The subway graph below has many cycles. Let's trace some of them:

  • Finsbury Park - ... - Kings Cross - ... - Old St - ... - Finsbury Park

  • Kings Cross - Euston - ... - British Museum - ... - Bank - ... - Kings Cross

  • Trafalgar Square - ... - Oxford Circus - ... - Bank - ... - Elephant & Castle - ... - Trafalgar Square

  You can entertain yourself by taking a virtual tour over the London Underground and trying to find more cycles!

• Weighted graph: In this type of graph, every edge is associated with a number, much like we correlate distances with roads connecting different locations. This type of graph is also extremely useful in many real-life applications, like logistics and engineering - the weight of the edge can be used to represent the time required to travel from one point to another, for example.

• Trees. A 'tree' is a connected graph that has no cycles. Sometimes, trees are required to be undirected, but that is more a matter of convention between mathematicians and computer scientists. If you wish to know more about trees, you can refer to a specific topic about them. Feel free to explore!

Note that the various types of graphs we've described are not mutually exclusive. That is, a tree can be weighted and (partially) directed, and so can a cyclic graph. But, of course, a cyclic graph can never be a tree and vice versa: trees cannot contain cycles simply by their definition.

Graph Representation

We already know that graphs are incredibly useful in solving lots of problems. But how can we implement a graph-based data structure in programming? Let's take a look at common concepts used by software engineers to represent a graph with $n$ vertices and $m$ edges.

1. Adjacency list. This is an array of $n$ lists where each list stores vertices connected to the respective node. This implementation works well for sparse graphs that do not have many edges compared to the number of vertices. It has a memory complexity of $O(n+m)$, which is very efficient. Here are some runtime estimates for this representation:

• Building the list takes $O(m)$, but for the worst-case scenario when every pair of vertices is linked, it will take $O(n^2)$.

• Removing a node can be done in $O(n^2)$.

• Removing an edge costs $O(n)$.

Below is an example showing an adjacency list for the graph we've already seen.

2. Adjacency matrix. This is a two-dimensional array forming an $n \times n$ matrix. Each entry indicates the presence of an edge in a graph. For undirected graphs without loops, adjacency matrices are always symmetric with zeros on the main diagonal. In weighted graphs, we use the weights of edges instead of $1$s to represent connectivity. Although it uses $O(n^2)$ memory, it has the following runtimes for some operations:

• Building a matrix takes $O(n^2)$ time, just as well as memory does.

• Removing a vertex costs $O(n)$.

• Removing an edge takes $O(1)$.

The adjacency matrix for the graph above is as follows:

If you are curious and want to know more about graph representation, try exploring this lesson. It offers more exciting ways of graph representation and provides an in-depth time-memory analysis. For instance, check the comprehensive table of time estimates below:

Conclusion

In conclusion, we learned:

1. The definition of a graph, its compartments and subtleties about edges and vertices.

2. The types of graphs: directed, cyclic, weighted, and trees.

3. How to represent graphs: adjacency list and adjacency matrix, including some of their runtime and memory complexities.

Hopefully, you now have an understanding of the basics of graphs necessary for moving on to more advanced topics. See you there!