Types of Graph

After understanding what a graph is, it’s essential to recognize that graphs come in many different varieties. Each type has unique properties and is suited for specific real-world applications.

In this post, we’ll explore all the major graph types with definitions, examples, and visual representations.

1. Directed Graph (Digraph)

A directed graph is a graph where all the edges have a direction. Each edge points from one vertex to another, and the relationship is one-way.

Representation

• Edge: u → v (from vertex u to vertex v)
• You can travel from u to v, but not necessarily from v to u.

Real-World Examples

• Twitter: You can follow someone, but they may not follow you back.
• Web Page Links: Page A linking to Page B doesn't mean Page B links back.
• Workflow/Task Dependencies: Task A must finish before Task B starts.

A → B
↓   ↓
C → D

(Edges have arrows indicating direction)

2. Undirected Graph (Bidirectional)

An undirected graph is a graph where all edges are bidirectional. The relationship is mutual – if there's an edge between u and v, you can travel both ways.

Representation

• Edge: (u, v) or u — v

Real-World Examples

• Social Networks (Facebook): If A is friends with B, B is also friends with A.
• Road Maps with Two-Way Streets: You can drive both directions on a street.
• Collaboration Networks: If person A works with person B, they collaborate mutually.

A — B
|   |
C — D

(Lines have no arrows, indicating mutual connection)

3. Complete Graph

A complete graph is a graph where every pair of distinct vertices is connected by a unique edge.

Properties

• Number of edges in an undirected complete graph with n vertices:
• Edges = n(n - 1) / 2

Real-World Examples

• Theoretical Models: Used in network design to guarantee maximum connectivity.
• Tournament Scheduling: Each team plays every other team exactly once.

    A
   /|\
  B-|-C
   \|/
    D

(Every vertex is connected to every other vertex)

4. Regular Graph

A regular graph is a graph where every vertex has the same degree (same number of neighbors).

Properties

• If every vertex has degree k, it's called a k-regular graph.
• A complete graph with n vertices is (n-1)-regular.

Real-World Examples

• Network Topologies: Used in designing efficient networks where each node has the same number of connections.
• Cubic Graphs (3-regular): Often used in graph theory problems.

A — B
|   |
D — C

(All vertices have degree 2 → 2-regular graph)

5. Cyclic Graph

A cyclic graph is a graph that contains at least one cycle (a path that starts and ends at the same vertex).

Real-World Examples

• Circular Dependencies: Task A depends on B, and B depends on A (deadlock).
• Infinite Loops: In state machines, to be detected and prevented.

A → B
↑   ↓
D ← C

(Forms a cycle: A → B → C → D → A)

6. Acyclic Graph

An acyclic graph is a graph that contains no cycles.

Special Cases

• Undirected Acyclic Graph: Always a Tree (connected) or Forest (disconnected).
• Directed Acyclic Graph (DAG): A directed graph with no cycles. Used extensively in scheduling.

Real-World Examples

• Task Scheduling: Tasks flow in one direction without loops.
• Compilation Order: Source files compiled in the correct order.
• Data Processing Pipelines: Data flows from source to destination without looping back.

A → B → C
    ↓
    D

(No path that returns to the starting vertex)

7. Weighted Graph

A weighted graph is a graph where each edge has a numerical value (weight) assigned to it.

Properties

• Weight can represent cost, distance, time, capacity, etc.
• Also called a network.

Real-World Examples

• GPS/Maps Applications: Weights represent distance or travel time between cities.
• Network Routing: Weights represent bandwidth or latency.
• Airline Networks: Weights represent flight cost or duration.

A --(5)-- B
|         |
(3)      (2)
|         |
C --(4)-- D

(Each edge has a number representing its weight)

8. Unweighted Graph

An unweighted graph is a graph where edges do not have any numerical values.

Real-World Examples

• Friend Networks: Either A is friends with B (1) or not (0).
• Web Pages: Either Page A links to Page B or not.
• Social Connections: Simple presence or absence of a relationship.

9. Connected Graph

A connected graph is an undirected graph where there is at least one path between every pair of vertices.

Real-World Examples

• Internet Topology: Ensuring all users can reach all websites.
• Network Topology Validation: Ensuring all nodes are reachable.

A — B
|   |
C — D

(All vertices are reachable from any other vertex)

10. Disconnected Graph

A disconnected graph is an undirected graph where some vertices are not reachable from others.

Components

• Each connected subset is called a connected component.

Real-World Examples

• Fault Detection: Identifying isolated sections in a network.
• Isolated Subgroups: Finding communities that don't interact.

A — B     C — D

(Group 1: A-B, Group 2: C-D → No connection between groups)

11. Simple Graph

A simple graph is a graph that has:

1. No self-loops (no edge from a vertex to itself).
2. No multiple edges (no parallel edges between the same pair).

Real-World Examples

• Most Standard Graph Problems: Textbook problems typically assume simple graphs.
• Social Networks (simple): One friendship per pair of people.

A — B
|   |
D — C

(Only one edge between any two vertices, no vertex connected to itself)

12. Multigraph

A multigraph is a graph that allows:

1. Multiple edges between the same pair of vertices (parallel edges).
2. May also allow self-loops.

Real-World Examples

• Transportation Networks: Multiple roads/railways between two cities.
• Packet Routing Paths: Multiple paths between network nodes.

A === B
|     |
C === D

(Double lines indicate multiple edges between the same vertices)

13. Directed Acyclic Graph (DAG)

A Directed Acyclic Graph (DAG) is a directed graph that has no cycles. You cannot return to the same vertex once you move forward.

Properties

• Often used to represent partial order of tasks.
• Can always be topologically sorted.

Real-World Examples

• Topological Sorting: Ordering tasks with dependencies.
• Task Scheduling: Airline flight scheduling, university course prerequisites.
• Build Systems: Makefiles (a file depends on others, but no circular dependencies).

A → B → C
↓
D → E

(No path forms a cycle)

14. Bipartite Graph

A bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V, such that every edge connects a vertex in U to one in V.

Properties

• No edges between vertices in the same set.
• Often used in matching problems.

Real-World Examples

• Matching Problems: Job assignment (one person assigned to one job).
• Network Flow: Modeling flows between two sets.
• Recommendation Systems: Users and items (ratings).

U: A   B   C
   |\  |  /|
V: D   E   F

(Edges only go between U and V, never within the same set)

15. Tree (as a Special Graph)

A tree is a connected acyclic undirected graph. It's a special type of graph with no cycles and exactly one path between any two vertices.

Properties

• Has n vertices and n-1 edges.
• Every tree is a graph, but not every graph is a tree.

Real-World Examples

• File Systems: Directory structures.
• Hierarchical Data: Organization charts, family trees.

    A
   / \
  B   C
     / \
    D   E

(No cycles, one unique path between any two vertices)

Summary Comparison Table