Below is a clear, simple, and exam-oriented explanation of Directed Graphs and Undirected Graphs — perfect for BCA/MCA/Engineering/Discrete Mathematics or Graph Theory exams.
⭐ Graph: Directed and Undirected
A graph is a mathematical structure used to model relationships between objects.
Objects are represented as vertices (nodes) and connections as edges.
Formally:
[
G = (V, E)
]
Where:
- (V) = set of vertices
- (E) = set of edges
Graphs are classified mainly into:
- Undirected Graphs
- Directed Graphs (Digraphs)
⭐ 1. Undirected Graph
In an undirected graph, edges do not have direction.
If ((u, v)) is an edge, then:
[
(u, v) = (v, u)
]
Meaning:
u is connected to v both ways.
⭐ Definition
A graph ( G = (V, E) ) is undirected if each edge is an unordered pair:
[
e = {u, v}
]
⭐ Example
Vertices:
[
V = {A, B, C}
]
Edges:
[
E = {(A, B),(B, C),(A, C)}
]
This is an undirected triangle graph.
⭐ Degree of a vertex
Degree = number of edges incident to the vertex.
Used in:
- Euler paths
- Graph connectivity
- Social network analysis
⭐ Applications of Undirected Graphs
✔ Social networks (friendship relations)
✔ Road maps (two-way roads)
✔ Electric circuits
✔ Telephone networks
✔ Computer networks (if bidirectional)
⭐ 2. Directed Graph (Digraph)
In a directed graph, edges have direction, like arrows.
If ⟨u, v⟩ is an edge, then:
[
\langle u, v \rangle \neq \langle v, u \rangle
]
Meaning:
There is a connection from u to v, but not necessarily from v to u.
⭐ Definition
A directed graph ( G = (V, E) ) has edges as ordered pairs:
[
E = { \langle u, v \rangle : u, v \in V }
]
⭐ Example
Vertices:
[
V = {A, B, C}
]
Edges:
[
E = {\langle A, B \rangle, \langle B, C \rangle, \langle C, A \rangle}
]
This forms a directed cycle.
⭐ In-degree and Out-degree
For a vertex v:
- In-degree = number of edges coming into v
- Out-degree = number of edges going out of v
Important in:
- PageRank
- Network flow
- Deadlock detection
⭐ Applications of Directed Graphs
✔ Web pages (links are directional)
✔ Traffic maps (one-way streets)
✔ Precedence tasks in scheduling
✔ State transition diagrams (automata theory)
✔ Dependency graphs
✔ Social networks (follower-following)
⭐ 3. Differences Between Directed and Undirected Graphs
| Feature | Undirected Graph | Directed Graph |
|---|---|---|
| Edge | No direction | Has direction |
| Edge notation | (u, v) | ⟨u, v⟩ |
| Vertex degrees | Degree | In-degree & Out-degree |
| Symmetry | (u,v) = (v,u) | ⟨u,v⟩ ≠ ⟨v,u⟩ |
| Path | No direction constraint | Follows direction of edges |
| Example | Road map | Web links |
| Applications | Networks, social graphs | Automata, scheduling |
⭐ 4. Mixed Graph
Sometimes graphs have both directed and undirected edges.
These are called mixed graphs.
Example:
- Transportation systems (two-way & one-way roads)
⭐ 5. Adjacency Representation Differences
✔ Undirected graph adjacency matrix
Symmetric matrix.
✔ Directed graph adjacency matrix
Not necessarily symmetric.
⭐ 6. Connectivity Differences
✔ Undirected graph
- Connected vs disconnected.
✔ Directed graph
- Strongly connected
- Weakly connected
⭐ Quick Exam-Oriented Summary
Undirected graph:
Edges have no direction.
Edge: (u, v) = (v, u).
Use: networks, social graphs.
Directed graph (digraph):
Edges have direction.
Edge: ⟨u, v⟩ ≠ ⟨v, u⟩.
Use: web links, state diagrams, dependencies.
Key terms:
- Degree (undirected)
- In-degree, out-degree (directed)
- Path, cycle, connectivity