By:- Ali Sir

Graph
A graph is a non-linear data
structure consisting of nodes or
vertices connected by edges. It is
used to represent relationships
between objects or entities.

Types of Graphs
1. Directed Graph: A graph in
which edges have direction.
2. Undirected Graph: A graph in
which edges do not have
direction.
3. Weighted Graph: A graph in
which edges are assigned weights
or labels.
4. Unweighted Graph: A graph in
which edges do not have weights
or labels.

By:-Ali Sir
Applications of Graphs
1. Social Network Analysis:
Graphs are used to model
relationships between people in
social networks.
2. Traffic Routing: Graphs are
used to optimize traffic routing
and navigation.
3. Computer Network Topology:
Graphs are used to model
computer network topology.
4. Recommendation Systems:
Graphs are used to build
recommendation systems.
Graph Terminology
1. Vertex (Node): A point in the
graph.
2. Edge: A connection between
two vertices.
3. Neighbor: A vertex that is
connected to another vertex.
4. Degree: The number of edges
incident on a vertex.
Connected and Disconnected
Graphs
A graph can be classified as
connected or disconnected based
on the connectivity of its vertices.

Connected Graph
A graph is said to be connected if
there is a path between every
pair of vertices. In other words, it
is possible to reach any vertex
from any other vertex by
traversing the edges of the
graph.

Disconnected Graph
A graph is said to be
disconnected if it is not
connected. In other words, there
are at least two vertices that are
not connected by any path.

Example
Consider a graph with 5 vertices:
A, B, C, D, and E.
- Connected Graph: If the edges
are (A, B), (B, C), (C, D), (D, E), (E,
A), then the graph is connected
because there is a path between
every pair of vertices.
- Disconnected Graph: If the
edges are (A, B), (B, C), (D, E),
then the graph is disconnected
because there is no path between
vertices A and D, or between
vertices A and E, etc.

Properties
- Connected Graph: A connected
graph has a single connected
component.
- Disconnected Graph: A
disconnected graph has multiple
connected components.
Applications
- Network Topology: Connected
graphs are used to model
networks where all devices are
reachable from each other.
- Social Network Analysis:
Disconnected graphs can
represent social networks where
there are distinct groups of
people who do not interact with
each other.
Connected/Disconnected Graphs
vs Directed/Undirected Graphs
These are two different concepts
in graph theory.

Connected/Disconnected Graphs
- Connected Graph: A graph
where there is a path between
every pair of vertices.
- Disconnected Graph: A graph
where there are at least two
vertices that are not connected
by any path.

Directed/Undirected Graphs
- Directed Graph: A graph where
edges have direction, represented
by arrows. The direction of the
edge matters.
- Undirected Graph: A graph
where edges do not have
direction. The connection
between vertices is bidirectional.

Key Differences
1. Connectivity:
Connected/disconnected graphs
refer to the existence of paths
between vertices.
2. Edge Direction:
Directed/undirected graphs refer
to the directionality of edges.

Example
- A graph can be connected and
directed, meaning there is a path
between every pair of vertices,
and the edges have direction.
- A graph can be disconnected
and undirected, meaning there
are vertices that are not
connected, and the edges do not
have direction.
Applications
- Connected/Disconnected:
Relevant in network topology,
social network analysis, and
traffic routing.
- Directed/Undirected: Relevant in
modeling relationships, traffic
flow, and dependencies.
Subgraph
A subgraph is a graph whose
vertices and edges are a subset
of a larger graph.

Example
Suppose we have a graph G with
vertices {A, B, C, D, E} and edges
{(A, B), (B, C), (C, D), (D, E), (E,
A)}.
A subgraph of G could be a graph
with vertices {A, B, C} and edges
{(A, B), (B, C)}.

Path Graph
A path graph is a graph where
vertices are connected in a linear
sequence, with each vertex
having degree 1 or 2, except for
the two end vertices which have
degree 1.

Example
A path graph with 4 vertices could
be represented as: A -- B -- C -- D.

Cycle Graph
A cycle graph is a graph where
vertices are connected in a cycle,
with each vertex having degree 2.

Example
A cycle graph with 4 vertices
could be represented as: A -- B --
C -- D -- A.

Properties
- Path Graph: Has two vertices
with degree 1 and the rest with
degree 2.
- Cycle Graph: All vertices have
degree 2.

Applications
- Path Graph: Represents a linear
sequence or a path in a network.
- Cycle Graph: Represents a
circular structure or a cycle in a
network.
📌 Basic Terminology in Graphs
1. Vertex (Node / Point)

 Fundamental unit of a graph.

 Represented by dots or circles.
 Example: In a social network, each person is a vertex.

2. Edge (Link / Line / Connection)

 A connection between two vertices.

 Example: Friendship between two people.

3. Adjacent Vertices (Neighbors)

 Two vertices are adjacent if there is an edge between them.

 Example: If A–B is an edge, then A and B are adjacent.

4. Degree of a Vertex

 Undirected Graph:
o Degree = Number of edges incident on the vertex.
o Example: If vertex A is connected to 3 vertices, degree(A) = 3.
 Directed Graph (Digraph):
o In-degree: Number of edges coming into the vertex.
o Out-degree: Number of edges going out from the vertex.
5. Path

 A sequence of vertices connected by edges.

 Example: Path A → B → C → D.

6. Cycle

 A path that starts and ends at the same vertex without repeating edges.
 Example: A → B → C → A.

7. Connected Graph

 A graph is connected if there is a path between every pair of vertices.

8. Disconnected Graph

 A graph that has at least two components with no path between them.

9. Subgraph

 A smaller graph taken from part of a larger graph.

10. Complete Graph (Kn)

 A graph where every pair of vertices is connected by an edge.

 Example: In K4 (4 vertices), every vertex is connected to all others.

11. Weighted Graph

 A graph where edges have weights (cost, distance, time).

12. Directed Graph (Digraph)

 A graph where edges have direction (arrows).

13. Loop (Self-loop)

 An edge that starts and ends at the same vertex.

14. Multiple Edges (Parallel Edges)

 More than one edge between the same pair of vertices.

15. Tree

 A connected graph with no cycles.

16. Isolated Vertex

 A vertex with degree 0 (not connected to any other vertex).

📌 Connected Graph
Definition

A Connected Graph is an undirected graph in which there is a path between every pair of
vertices.

 This means you can travel from any vertex to any other vertex by following edges.

✅ Example
Consider a graph with vertices: {A, B, C, D}
Edges: {A–B, B–C, C–D, A–D}

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

 From A, you can reach B, C, and D.

 From B, you can reach A, C, D.
 From C, you can reach A, B, D.
 From D, you can reach A, B, C.

👉 Since every pair of vertices is connected, this is a Connected Graph.

📌 Disconnected Graph (for contrast)

Vertices: {A, B, C, D}
Edges: {A–B, C–D}

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

 Here, A and B are connected.

 C and D are connected.
 But A cannot reach C or D.

👉 So this is a Disconnected Graph.

📌 Applications of Connected Graphs

 Road networks (every city connected).
 Computer networks (devices connected).
 Electrical circuits.
 Social networks (all users connected in a community).

📌 Disconnected Graph
Definition

A Disconnected Graph is a graph in which at least one pair of vertices is not connected by
any path.
👉 In simple words: the graph is split into two or more separate parts (components).

✅ Example
Vertices: {A, B, C, D}
Edges: {A–B, C–D}

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

 Here, A and B are connected.

 C and D are connected.
 But there is no path from A or B to C or D.

👉 This graph is Disconnected because it has two components.

📌 Key Points
 A Connected Graph has 1 component.
 A Disconnected Graph has 2 or more components.
 If a graph has isolated vertices (degree = 0), it is also disconnected.

📌 Applications / Situations
 In computer networks: If some computers are not connected to the internet, the network
becomes disconnected.
 In social networks: If a group of people are not connected to the rest, they form a
disconnected component.

📌 Subgraph
Definition

A Subgraph is a smaller graph that is formed from a part of a larger graph.

 It contains a subset of vertices and a subset of edges from the original graph.
 Formally: If G=(V,E)G = (V, E)G=(V,E), then a subgraph G′=(V′,E′)G' = (V', E')G′=(V
′,E′) where
o V′⊆VV' \subseteq VV′⊆V
 o E′⊆EE' \subseteq EE′⊆E

✅ Example
Original Graph GGG:

Vertices = {A, B, C, D}
Edges = {A–B, B–C, C–D, A–D, B–D}

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

Possible Subgraph G′G'G′:

Vertices = {A, B, D}
Edges = {A–B, A–D}

A ----- B
|
D

👉 This smaller graph is a subgraph of the original graph.

📌 Types of Subgraphs
1. Proper Subgraph:
o A subgraph that is not equal to the original graph.
o Example: Taking only part of the graph.
2. Induced Subgraph:
o If we take a subset of vertices V′, then include all edges from E that connect
those vertices.

📌 Applications of Subgraphs
 Studying smaller portions of a large network.
 Analyzing communities in social networks.
 Detecting patterns or structures within large graphs.
📌 Directed Graph (Digraph)
A Directed Graph (or Digraph) is a type of graph where edges have direction.

Formally:

G=(V,E)G = (V, E)G=(V,E)

 VVV = set of vertices

 EEE = set of ordered pairs (u,v)(u, v)(u,v), meaning an edge goes from u → v

📌 Example
 Twitter: If A follows B, it does not mean B follows A.
 This is represented as an arrow: A → B.

📌 Representation of a Digraph
1. Adjacency Matrix

For a graph with nnn vertices:

 matrix[i][j]=1matrix[i][j] = 1matrix[i][j]=1 if an edge exists from i→ji \to ji→j

 Otherwise, 0

Example:
Vertices = {A, B, C}
Edges = {A → B, B → C, A → C}

Adjacency Matrix:

A B C
A 0 1 1
B 0 0 1
C 0 0 0

2. Adjacency List
A → [B, C]
B → [C]
C → []

📌 Special Types of Digraphs

1. Weighted Digraph: Each directed edge has a weight.
Example: Roads with distances (A → B = 5 km).
2. Strongly Connected Digraph: Every vertex can be reached from every other vertex by
following directions of edges.
3. Weakly Connected Digraph: If directions are ignored, the graph is connected.
4. Acyclic Digraph (DAG - Directed Acyclic Graph):
o A directed graph with no cycles.
o Example: Task scheduling (one task must be completed before another).

📌 Applications of Digraphs
 Web Links: Page A linking to Page B.
 Social Media: Twitter/Instagram (follow relation).
 Task Scheduling: Dependencies in project planning.
 Compiler Design: Order of execution (topological sorting).
 Computer Networks: Data routing with direction.

Eulerian Graph

 Definition:
A graph is Eulerian if there exists a closed trail (called an Eulerian circuit) that visits
every edge exactly once and starts and ends at the same vertex.
 Key Point:
Eulerian graphs focus on edges — you must cover all edges once.
 Condition for Undirected Graph:
A connected graph is Eulerian if every vertex has an even degree (an even number of
edges connected to it).
 Example:
Consider a square with diagonals:
 A
 / \
 B---C
 \ /
 D

Edges: AB, BC, CD, DA (square edges), plus diagonals AC and BD.
 o Each vertex has an even degree (4 edges touching each vertex).
o You can start at A and travel through each edge once and return to A.

Hamiltonian Graph

 Definition:
A graph is Hamiltonian if there exists a cycle (called a Hamiltonian cycle) that visits
every vertex exactly once and returns to the starting vertex.
 Key Point:
Hamiltonian graphs focus on vertices — you must cover all vertices once.
 No simple condition like Eulerian graphs; checking Hamiltonicity is more complex (NP-
complete problem).
 Example:
Consider the same square with diagonals:
 A
 / \
 B---C
 \ /
 D
o A Hamiltonian cycle could be: A → B → D → C → A (visits all vertices once,
returns to A).

Summary Table

Property Eulerian Graph Hamiltonian Graph

Visits Every edge exactly once Every vertex exactly once
Starts and ends at the same
Ends Starts and ends at the same vertex
vertex
Main focus Edges Vertices
Condition No simple necessary and sufficient
Every vertex has even degree
(Undirected) condition
Complexity to check Easy (polynomial time) Hard (NP-complete)
Graph with all even degree
Example Graph with a cycle through all vertices
vertices

Trees (Graph Theory)

What is a Tree?
  A tree is a special type of graph that is:
o Connected: There is a path between every pair of vertices.
o Acyclic: It contains no cycles (no closed loops).

Properties of Trees

1. Number of edges:
If a tree has n vertices, it always has n - 1 edges.
2. Unique path:
Between any two vertices in a tree, there is exactly one unique path.
3. Connected and acyclic:
A tree is connected and has no cycles.
4. Adding edges:
Adding any edge to a tree creates a cycle.
5. Removing edges:
Removing any edge disconnects the tree.
6. Leaves:
Vertices with degree 1 are called leaves or pendant vertices.

Example of a Tree
A
/ \
B C
/ / \
D E F

 Vertices: A, B, C, D, E, F (6 vertices)
 Edges: AB, AC, BD, CE, CF (5 edges = 6 - 1)
 No cycles, connected.
 Unique path between any two vertices.

2. Spanning Tree Definition

 A spanning tree of a connected graph is a subgraph that:

1. Includes all the vertices of the original graph.
2. Is a tree (no cycles, and is connected).
3. Has exactly (V – 1) edges, where V is the number of vertices in the graph.

So, a spanning tree "spans" all the vertices with the minimum number of edges needed to keep
them connected.

3. Key Properties
  If the graph has V vertices, each spanning tree has V – 1 edges.
 A graph may have many different spanning trees.
 Removing any edge from a spanning tree will disconnect it.
 Adding any extra edge to a spanning tree will form a cycle.

4. Example

Suppose we have a graph with 4 vertices: A, B, C, D.

Graph edges:

 A–B, A–C, B–C, B–D, C–D

One possible spanning tree:

 A–B, A–C, B–D

(This connects all 4 vertices, has 3 edges, and no cycles.)

Another spanning tree:

 A–C, C–D, B–C

5. Special Types

 Minimum Spanning Tree (MST): If edges have weights (cost, distance, etc.), then a
spanning tree with the minimum total weight is called an MST.
o Famous algorithms: Kruskal’s Algorithm and Prim’s Algorithm.

✅ In short:
A spanning tree is a tree that connects all vertices of a graph using the fewest edges possible
(V–1), without forming cycles.
Here’s a clear visualization:

 On the left, you see the original graph with multiple connections (including cycles).
 On the right, you see one possible spanning tree of the graph:
o All vertices are connected.
o It has exactly V – 1 = 3 edges.

No cycles are present

Do you want me to also show how the minimum spanning tree (MST) is chosen
when edges have weights?

Here you can see:

 On the left, the weighted graph (numbers on edges are weights/costs).

 On the right, the Minimum Spanning Tree (MST):
o It connects all vertices.
o Has V – 1 edges (3 edges for 4 vertices).
o Chooses edges with the minimum total weight (1 + 2 + 3 = 6).
Would you like me to also explain step by step how Kruskal’s or Prim’s
algorithm builds this MST?

Perfect 👍 Let’s go step by step with both algorithms on the same weighted graph:

Graph edges with weights:

 A–B (4)
 A–C (2)
 B–C (1)
 B–D (5)
 C–D (3)

🔹 1. Kruskal’s Algorithm (edge-based)

Idea: Always pick the smallest weight edge that doesn’t form a cycle.

Steps:

1. Sort edges by weight → (B–C:1), (A–C:2), (C–D:3), (A–B:4), (B–D:5)

2. Pick B–C (1) → no cycle.
3. Pick A–C (2) → no cycle.
4. Pick C–D (3) → no cycle.
5. Stop (we already have 3 edges = V–1).

✅ MST = {B–C, A–C, C–D}, Total weight = 6.

🔹 2. Prim’s Algorithm (vertex-based)

Idea: Start from any vertex, always pick the smallest edge connecting to a new vertex.

Steps (start from A):

1. From A → smallest edge is A–C (2).

MST = {A–C}, visited = {A, C}.
2. From {A, C} → smallest connecting edge is C–B (1).
MST = {A–C, C–B}, visited = {A, B, C}.
3. From {A, B, C} → smallest connecting edge to new vertex is C–D (3).
MST = {A–C, C–B, C–D}.

✅ MST = {A–C, C–B, C–D}, Total weight = 6.

✨ Observation

Both Kruskal’s and Prim’s give the same MST (though the process is different).

Would you like me to also make a step-by-step visual animation (graphs at each step) so you
can see how the MST is built?

Here’s the step-by-step Kruskal’s Algorithm visualization:

 Step 1: Edge B–C (1) is chosen.

 Step 2: Edge A–C (2) is added (still no cycle).
 Step 3: Edge C–D (3) is added, completing the spanning tree.

👉 After 3 steps (V–1 edges), the MST is formed.

Do you also want me to create the step-by-step animation for Prim’s Algorithm in the same
way?

Prim’s Algorithm (Starting from A)

Graph edges with weights:

 A–B (4)
 A–C (2)
 B–C (1)
 B–D (5)
 C–D (3)

🔹 Step 1: Start from A

 Possible edges: A–B (4), A–C (2)

  Pick the smallest: A–C (2)
 MST = {A–C}, visited = {A, C}

🔹 Step 2: From {A, C}

 Possible edges: C–B (1), C–D (3), A–B (4)

 Pick the smallest: C–B (1)
 MST = {A–C, C–B}, visited = {A, B, C}

🔹 Step 3: From {A, B, C}

 Possible edges: C–D (3), B–D (5)

 Pick the smallest: C–D (3)
 MST = {A–C, C–B, C–D}, visited = {A, B, C, D}

✅ Final MST = {A–C (2), C–B (1), C–D (3)}

👉 Total Weight = 6

Feature Kruskal’s Algorithm Prim’s Algorithm

Edge-based: Always picks the Vertex-based: Starts from one vertex
Approach
smallest edge (avoiding cycles) and grows the tree step by step
No full sorting needed; uses greedy
Sorting Requires sorting all edges by weight
selection with priority queue/heap
Uses Union-Find (Disjoint Set) to Cycles are naturally avoided (since tree
Cycle Handling
avoid cycles expands gradually)
Best for Graph Works better for sparse graphs Works better for dense graphs (more
Type (fewer edges) edges)
Doesn’t matter (no fixed start
Starting Point Must start from a chosen vertex
vertex)
O(E log E), where E = number of O(E + V log V), where V = vertices, E =
Time Complexity
edges edges
Example (Our Steps: B–C (1), A–C (2), C–D (3) Steps: A–C (2), C–B (1), C–D (3) →
Graph) → Total weight = 6 Total weight = 6
Kruskal’s Algorithm Prim’s Algorithm
 Feature Kruskal’s Algorithm Prim’s Algorithm

Feature
Vertex-based: किसी एक vertex से
Edge-based: हर बार सबसे छोटा
Approach शुरू करता है और नए vertex जोड़ता
edge चुनता है (cycle न बने)
है
Sorting की ज़रूरत नहीं, priority
सभी edges को weight के अनुसार
Sorting queue / greedy selection से काम चलता
sort करना पड़ता है
है
Cycle बनने की समस्या naturally
Cycle चेक करने के लिए Union-
Cycle Handling avoid होती है (क्योंकि step-by-step
Find (Disjoint Set) का उपयोग
grow करता है)
Graph Type Sparse graphs (कम edges) के लिए Dense graphs (ज़्यादा edges) के
Suitability अच्छा लिए अच्छा
किसी भी vertex से फर्क नहीं हमेशा किसी एक vertex से शुरू
Starting Point
पड़ता करना पड़ता है
O(E + V log V) (V = vertices, E =
Complexity O(E log E) (E = edges)
edges)
Example (Our Steps: B–C (1), A–C (2), C–D (3) Steps: A–C (2), C–B (1), C–D (3) →
Graph) → Weight = 6 Weight = 6

👉 Conclusion:

 Kruskal’s is simpler when the graph is sparse and edges are easily sortable.
 Prim’s is more efficient for dense graphs and when using adjacency matrix/priority
queue.
 Both always produce the same Minimum Spanning Tree (MST) ✅.