Basic Terminology in Graph Theory

A graph is made up of several nodes (Vertex) and edges (Edge). Here are some key points:

• 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 diagram below shows a directed unweighted 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 directly from 3 to 1.

Here 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 write code, we usually treat undirected edges as two directed edges in both directions.

Here is a directed weighted graph:

Here is an undirected weighted graph:

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

Many classic graph algorithms are based on weighted graphs, such as finding the shortest path and the minimum spanning tree. We will talk about these in later sections.

Degree

Each node in a graph has a degree.

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

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

In a directed graph, each node's degree is split into indegree (number of incoming edges) and outdegree (number of outgoing edges).

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

Relationship Between Number of Nodes and Edges

Most graphs we discuss are "simple graphs", which means 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 of $E$?

The minimum value of $E$ is 0, which means only nodes, no edges.

For the maximum, each node can connect to $V-1$ other nodes. So the maximum 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

A subgraph is a basic concept in graph theory.

Subgraph: If all nodes and edges of graph $G'$ are in graph $G$, then $G'$ is a subgraph of $G$. In simple words, a subgraph is made by deleting some nodes and edges from the original graph.

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

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

The graph 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: A subgraph made by choosing some nodes from the original graph, and keeping all edges between these nodes that exist in the original graph.

The graph below is an induced subgraph of $G$. It contains nodes 1,2,3,4 and all edges between them from the original graph.

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

Connectivity

Connectivity is a very important idea in graph theory. It tells us if 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, the graph is called connected.

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

Connected Component: In an undirected graph that is not connected, each group of connected nodes forms a connected component. A graph can have several connected components.

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

Connectivity in Directed Graphs

Connectivity is a bit more complex in directed graphs because we have to consider edge directions. There are two main ideas: strong connectivity and weak connectivity.

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. From any node, you can reach all other nodes following the edges' directions.

Weakly Connected Graph: If you ignore the direction of all edges, and the graph becomes connected, the original directed graph is weakly connected.

For example, the graph below is not strongly connected (you can't get from node 4 to node 1 following edge directions), but it is weakly connected if you ignore directions.

Strongly Connected Component (SCC): In a directed graph, a strongly connected component is a largest group of nodes where each node can reach every other node in the group following edge directions.

For example, the graph below has two SCCs: nodes 1~3 make one SCC, nodes 4~6 make another SCC.

Weakly Connected Component (WCC): After turning all directed edges into undirected edges, each connected group is a weakly connected component of the original directed graph.

There are many other complex terms in graph theory. But for learning data structures and algorithms, understanding these basic ideas is enough. When we learn more about real graph algorithms later, we will use these concepts.