Types of Graphs

Graphs can be classified in many ways depending on their structure and properties.

---

1. Based on Edge Direction

(a) Undirected Graph

• Edges have no direction.

• If there is an edge between $u$ and $v$, we can travel both ways.

• Example: Road between two cities without one-way restrictions.

👉 Diagram:

---

(b) Directed Graph (Digraph)

• Edges have direction.

• If there is an edge $⟨u,v⟩,\; you\; can\; go\; from$$u$ to $v$, but not necessarily from $v$ to $u$.

• Example: Twitter “follow” (A follows B does not mean B follows A).

👉 Diagram:

---

2. Based on Edge Weights

(a) Unweighted Graph

• All edges are equal, no weights.

• Example: Friendship network – either friends or not.

(b) Weighted Graph

• Each edge carries a weight (distance, cost, time, capacity).

• Example: In Google Maps, edges have weights = distance between cities.

👉 Diagram Example:

---

3. Based on Edge Multiplicity

(a) Simple Graph

• No multiple edges between the same pair of vertices.

• No self-loops (an edge from a vertex to itself).

(b) Multigraph

• More than one edge allowed between the same pair of vertices.

• May also allow self-loops.

• Example: Multiple bus routes between the same two cities.

---

4. Based on Connectivity

(a) Connected Graph (for undirected graphs)

• There is a path between every pair of vertices.

• Example: A road map where every city can be reached from any other city.

(b) Disconnected Graph

• At least one vertex is not reachable from others.

👉 Example Diagram:

A —— B     C —— D

Two disconnected components.

(c) Strongly Connected Graph (for directed graphs)

• In a directed graph, if there is a path from every vertex to every other vertex.

(d) Weakly Connected Graph

• If we ignore edge directions, the graph becomes connected, but with direction it may not be.

---

5. Based on Density

(a) Sparse Graph

• Very few edges compared to maximum possible edges.

• Typically $|E| \ll |V|^2$
  

(b) Dense Graph

• Large number of edges, close to maximum possible.

---

6. Special Types of Graphs

(a) Complete Graph (K$_n$)

• Every pair of vertices is connected by an edge.

• For $n$ vertices, number of edges = $\frac{n(n-1)}{2}$
  

👉 Example:

(b) Cycle Graph

• Graph where vertices form a closed loop.A graph with at least one cycle is called a cyclic graph

(c) Bipartite Graph

• Vertices divided into two sets, and every edge connects a vertex in one set to a vertex in the other set.

• Example: Students and Courses – edges show which student takes which course.

(e) Tree

• A special connected graph with no cycles.

• A tree with $n$ vertices always has $n-\mathrm{1\; edges.}$

---

Summary Table

Type	Description	Example
UnDirected	Edges have no direction	Road between two cities
Directed	Edges have direction	Twitter follow
Weighted	Edges have weights	Google Maps
Simple	No multiple edges/loops	Social friendship network
Multigraph	Multiple edges allowed	Bus routes
Connected	Path between all vertices	Road map
Disconnected	Not all vertices reachable	Isolated networks
Complete	Every vertex connected to every other	K$_n$
Bipartite	Vertices split into two sets	Students ↔ Courses
Tree	Connected, acyclic	File directory