General Definition

A Graph is one of the most fundamental but also diverse data structures in computer science. A Graph consists of a set of vertices $V$ and a set of edges $E$ where each edge is an unordered pair. Hence, $G=(V,E)$. They are used to represent relationships between various entities or elements (the vertices) by connecting them with edges.

For example, a graph can be used to represent a social network where the vertices are people and the edges represent whether they are friends with each other or not, no edge signifying that they are not friends. In the below graph $G=(V,E)$ where:

• $V=\{\text{Bob, Alice, Michael, Urs, Karen}\}$ and
• $E=\{(1,2),(1,3),(2,4),(2,5)\}$

Metrics

Degrees

If we do some quick analysis of this graph using the degree function which returns the number of edges connected to a vertex, we can see that $\text{deg(Alice)}=3$ and therefore Alice has the most friends in this social network.

Order

The order of a graph is the number of vertices in the graph. So in the above example, the order of the graph is 5. So it could also be called an order-5 graph.

Diameter

The diameter of a graph is the longest shortest path between two vertices in the graph. So in the above example, the diameter of the graph is 3 as the longest shortest path is between Michael and Karen.

Density

The density of a graph is the ratio of the number of edges to the number of possible edges. So in other words how densely connected the graph is. In a directed graph there are $|V|(|V|-1)$ possible edges. Which means the density of a directed graph is:

In an undirected graph, there are $\frac{|V|(|V|-1)}{2}$ possible edges. Which means the density of an undirected graph is:

So in the above example, the density of the graph is $\frac{8}{20} = 0.4$.

Graphs of Functions

You might be more familiar with Graphs when talking about mathematical functions. In mathematics, a Graph of a Function is a visual representation of the relationship between the input values (domain) and their corresponding output values (range) under a specific function.

Formally, a Graph of a Function can be defined as follows:

Let $f$ be a function defined on a set of input values, called the domain $D$, and taking values in a set of output values, called the range $R$. The Graph of the Function $f$, denoted as $G(f)$, is a mathematical representation consisting of a set of ordered pairs $(x, y)$, where $x \in D$ and $y = f(x)$. Each ordered pair represents a point on the graph, with $x$ as the independent variable (input) and $y$ as the dependent variable (output).

In other words, the Graph of a Function is a visual representation of how the elements in the domain are mapped to the corresponding elements in the range through the function $f$.

For example, consider the following function:

Its domain could be the set of all real numbers $\Bbb{R}$, and its range could also be $\Bbb{R}$. To represent this function graphically, we plot points on the Cartesian plane where the $x$-coordinate corresponds to the input value, and the $y$-coordinate is the output value obtained by evaluating $f(x)$.

Graphs of Functions play a crucial role in analyzing and understanding the behavior of functions and studying their overall patterns and trends.

Types of Graphs

Complete Graphs

A complete graph is a graph where each vertex is connected to every other vertex, very simple. In other words, a complete graph contains all possible edges. A complete graph with $n$ vertices is denoted as $K_n$.

For example, the below graph is a complete graph with 5 vertices, $K_5$.

Directed Graphs

A Directed Graph is a graph where each edge is directed from one vertex to another. In other words, the edges have a direction. The previous graph was an example of an undirected graph as we would hope that if person A thinks of person B as a friend then Person B feels the same way. However, in a directed graph, this is not necessarily the case.

So we can define a directed graph as $G=(V,A)$ where:

• V is again the set of vertices
• A is a set of ordered pairs of vertices, called arcs, arrows or directed edges (sometimes simply edges with the corresponding set named E instead of A). Ordered pairs are used here because (unlike for undirected graphs) the direction of an edge $(u,v)$ is important: $(u,v)$ is not the same edge as $(v,u)$. The first vertex is called the tail or initial vertex and the second vertex is called the head or terminal vertex.

For example, let us imagine a directed graph where the vertices are the same as the previous example but the edges signify if a person has liked another person's post on social media. We then get the below graph $G=(V,A)$ where:

• $V=\{\text{Bob, Alice, Michael, Urs, Karen}\}$ and
• $A=\{(1,2),(1,3),(2,4),(2,5),(5,2)\}$

When talking about degrees in a directed graph, we more often distinguish between the in-degree and out-degree of a vertex. The in-degree of a vertex is the number of edges that are pointing to that vertex and the out-degree is the number of edges that are pointing away from that vertex. So in the above example, the in-degree of Alice is 2 and the out-degree is also 2.

Weighted Graphs

A weighted graph is a graph where each edge has a weight (a number associated with it). It can be as a triple $G = (E, V, w)$ where $w$ is a function that maps edges or directed edges to their weights. So, $w: E \rightarrow \Bbb{R}$ could be a function for a graph with real numbers as weights.

For example, in a graph where each city is a vertex and each edge is a road between two cities, the weight could be the distance in km between them.

Networks vs Graphs

The only real difference between a network and a graph is the terminology. A network is a graph with a real-world context. For example, a social network is a graph with a real-world context. A graph is a mathematical structure that represents relationships between objects. When talking about a network we also tend to talk about nodes and links instead of vertices and edges.

Ressource (opens in a new tab)

Trees

A tree is a special type of graph where there is only one path between any two vertices. This means that there are no cycles in a tree. Trees are used in many different algorithms and data structures such as binary search trees. You can read more about trees in the Trees section.

Cycle/Circular Graphs

A cycle or circular graph is a graph with exactly one cycle. Where a cycle is non-empty path in which only the first and last vertices are equal, i.e a path that starts and ends at the same vertex. You can think of it as a closed chain.

A path/trail/walk in a graph is defined as being a sequence of vertices, where consecutive vertices in the sequence are connected by an edge.

Commonly a cycle with length $n$ is called an $n$-cycle and is denoted as $C_n$.

For example, the below graph is a circular graph as it has only one cycle with the following path:

To read more about cycle graphs, check out this article (opens in a new tab)

Acyclic Graphs

An acyclic graph is a graph that is almost the opposite of a cycle graph. It is a graph that has no cycles. This means that there is no path that starts and ends at the same vertex. A popular example of an acyclic graph is a tree.