Classification of Graph: Directed and Undirected Graphs

Definition

A graph is an ordered pair $G = (V, E)$ , where:

$V$ is a non-empty set of vertices
$E$ is a set of edges connecting the vertices

The two main classifications are:

Undirected Graph

A graph in which each edge has no direction. If there is an edge between vertex $u$ and vertex $v$ , then the relationship is bidirectional.

Directed Graph (Digraph)

A graph in which each edge has a direction from one vertex to another. If there is an edge from $u$ to $v$ , it does not necessarily mean there is an edge from $v$ to $u$ .

In formal notation:

Undirected edge: $\{u, v\}$
Directed edge: $(u, v)$ or $u \rightarrow v$

Examples:

Undirected: A friendship relation between Alice and Bob.
Directed: A “follows” relation on a social media platform, where Alice follows Bob, but Bob may not follow Alice.

Main Content

1. Undirected Graph

In an undirected graph, edges do not have arrows; they simply connect two vertices.
The edge $\{u, v\}$ means that $u$ is connected to $v$ and $v$ is connected to $u$ .

An undirected graph is used when the relation is symmetric. This means if one vertex is connected to another, the opposite connection is automatically assumed. For example, if two cities are connected by a two-way road, traveling is possible in both directions, so the graph is undirected.

Example:

A ----- B
|       |
|       |
C ----- D

In this graph:

A is connected to B and C
B is connected to A and D
C is connected to A and D
D is connected to B and C

Important properties of undirected graphs:

Degree of a vertex

The number of edges incident on that vertex.

No arrow direction

The edge relation is always mutual.

Symmetric adjacency matrix

If vertex $u$ is connected to $v$ , then $v$ is also connected to $u$ .

Real-life examples:

Friendship networks
Road networks with two-way streets
Electrical circuit connections
Communication links where data flows in both directions

2. Directed Graph

In a directed graph, every edge has a direction shown by an arrow.
The edge $(u, v)$ means there is a directed connection from $u$ to $v$ .

A directed graph is used when the relation is not necessarily symmetric. The direction matters because the connection may exist only one way. For example, in a web graph, a link from page A to page B does not imply a link from B to A.

Example:

A ---> B
^      |
|      v
C <--- D

In this graph:

A points to B
B points to D
D points to C
C points to A

Important properties of directed graphs:

In-degree

Number of edges entering a vertex.

Out-degree

Number of edges leaving a vertex.

Ordered pair edges

The order matters; $(u, v)$ is different from $(v, u)$ .

Adjacency matrix may not be symmetric

Because direction affects connection.

Real-life examples:

One-way traffic routes
Webpage hyperlinks
Task scheduling and dependencies
Social media “follow” relationships
Workflow pipelines

3. Comparison Between Directed and Undirected Graphs

In an undirected graph, the connection is mutual; in a directed graph, the connection has a source and destination.
The choice of graph type depends on the nature of the relationship being modeled.

A clear comparison can be understood by looking at how edges behave:

Feature	Undirected Graph	Directed Graph
Edge direction	No direction	Has direction
Edge notation	$\{u, v\}$	$(u, v)$
Symmetry	Symmetric	Not necessarily symmetric
Degree type	Degree	In-degree and out-degree
Common use	Mutual relationships	One-way relationships

Example of the same relation:

If A is friends with B, the graph is undirected.
If A follows B on social media, the graph is directed.

This classification is crucial because algorithms may behave differently depending on graph type. For example, traversal, cycle detection, shortest path, and topological sorting often depend on whether the graph is directed or undirected.

Working / Process

1. Identify the nature of the relationship

Determine whether the connection between objects is mutual or one-way.
If both directions are automatically valid, use an undirected graph.
If direction matters, use a directed graph.

2. Represent the graph correctly

For undirected graphs, store edges as pairs without direction.
For directed graphs, store each edge with an arrow-like direction from source to destination.
In adjacency lists, undirected graphs usually store each edge in both vertices’ lists, while directed graphs store it only in the source vertex’s list.

3. Analyze graph properties

For undirected graphs, calculate degree of each vertex.
For directed graphs, calculate in-degree and out-degree.
Use the correct algorithms and interpretations based on the graph type.

Example process:

Problem: Model a road network.
If roads are two-way, choose an undirected graph.
If roads are one-way, choose a directed graph.
Then build adjacency lists or matrices accordingly and apply graph algorithms.

Advantages / Applications

Accurate real-world modeling

Graph classification helps represent real systems correctly, such as friendships, roads, dependencies, and links.

Efficient algorithm design

Many algorithms depend on whether a graph is directed or undirected, making problem solving more efficient and correct.

Wide practical use

Used in social networks, computer networks, transportation systems, web search, project scheduling, and dependency analysis.

Summary

Directed graphs have arrows and show one-way relationships, while undirected graphs have no arrows and show mutual relationships.
The type of graph chosen depends on whether direction matters in the relationship being modeled.
Graph classification is essential for correct representation and algorithm selection.
Important terms to remember: vertex, edge, directed graph, undirected graph, in-degree, out-degree, adjacency matrix, adjacency list