Basic Terminology in Graph Theory

A graph is made up of several vertices (nodes) and edges. In detail:

• Each node has a unique ID.
• Edges can be directed (directed graph) or undirected (undirected graph).
• Edges can have weights (weighted graph) or no weights (unweighted graph).

Edge Weights and Directions

The following is a directed unweighted graph:

In the graph, there is a directed edge from node 1 to node 3. This means you can go from node 1 to node 3 directly. But there is no edge from node 3 to node 1, so you cannot go from 3 back to 1 directly.

The following is an undirected unweighted graph:

There is an undirected edge between node 1 and node 3. This means you can go from 1 to 3, and also from 3 to 1.

You can think of an undirected graph as a "two-way" graph. When we implement it in code, we usually add two directed edges for each undirected edge.

The following is a directed weighted graph:

Below is an undirected weighted graph:

Weighted graphs are very common in real life. For example, in a map app, the weight of an edge can be the distance between two places. In a logistics network, the weight can be the shipping cost between two locations.

Many classic graph algorithms are based on weighted graphs, such as finding the shortest path or the minimum spanning tree. These will be explained in later sections.

Degree

Each node in a graph has a degree.

In an undirected graph, the degree is the number of edges connected to the node.

For example, in the undirected graph below, node 1 has degree 2, and node 4 has degree 4.

In a directed graph, since edges have directions, the degree of a node is divided into indegree and outdegree.

For example, in the graph below, node 3 has indegree 2 (two edges point to it) and outdegree 1 (one edge goes out from it):

The Relationship Between the Number of Edges and Nodes

Usually, we discuss simple graphs, which means there are no self-loops and no multiple edges between the same two nodes.

In a simple graph, suppose there are $E$ edges and $V$ nodes. What is the possible range for the number of edges $E$?

The smallest value for $E$ is 0. This means there are only some nodes, and none of them are connected. This is allowed.

For the largest value, each node can connect to at most $V-1$ other nodes. So, the largest number of edges is $E = V(V-1)/2 \approx V^2$.

If $E$ is close to $V^2$, we call it a dense graph. If $E$ is much smaller than $V^2$, we call it a sparse graph.

Subgraph

In graph theory, the concept of a subgraph is important.

Subgraph: If all the nodes and edges of graph $G'$ are contained in graph $G$, then $G'$ is called a subgraph of $G$. Simply put, a subgraph is a graph that you get by removing some nodes and edges from the original graph.

Suppose the graph above is $G$. Let's explain two special types of subgraphs:

Spanning Subgraph: A subgraph that contains all the nodes of the original graph but only some of the edges.

Below is a spanning subgraph of $G$. It has all the nodes, but the edge between node 3 and node 4 is removed.

Induced Subgraph: Pick some nodes from the original graph, and include all the edges between these nodes that exist in the original graph.

Below is an induced subgraph of $G$. It contains nodes 1,2,3,4 and all the edges among them.

The concept of subgraphs is used in many graph algorithms. For example, when finding a minimum spanning tree, we are actually looking for a spanning subgraph with the smallest total weight.

Connectivity

In graph theory, connectivity is a very important idea. It tells us whether there is a path between nodes.

Connectivity in Undirected Graphs

Connected Graph: If there is a path between any two nodes in an undirected graph, we call it a connected graph.

The graph above is connected. You can go from any node to any other node.

Connected Component: If an undirected graph is not connected, each group of connected nodes is called a connected component. A graph may have several connected components.

For example, the following graph has two connected components: nodes 1~5 form one component, and nodes 6,7 form another.

Connectivity in Directed Graphs

Connectivity in directed graphs is a bit more complex, because the direction of edges matters. There are two types: strongly connected and weakly connected.

Strongly Connected Graph: If there is a directed path between any two nodes in a directed graph, the graph is called strongly connected.

For example, the graph below is strongly connected. You can go from any node to any other node.

Weakly Connected Graph: If you turn all the directed edges into undirected edges, and the graph becomes connected, then the original graph is weakly connected.

For example, the graph below is not strongly connected (you cannot go from node 4 to node 1), but it is weakly connected, because if you ignore the direction, all nodes are connected.

Strongly Connected Component (SCC): In a directed graph, each largest strongly connected subgraph is called a strongly connected component.

For example, the graph below has two strongly connected components: nodes 1~3 form one, and nodes 4~6 form another.

Weakly Connected Component (WCC): If you change all edges in a directed graph to undirected, each connected component in the new graph is a weakly connected component of the original graph.

There are many other terms in graph theory, but for learning data structures and algorithms, understanding the terms above is enough. Later, when we talk about specific graph algorithms, we will use these ideas in real problems.