Inaugurated by IN-SPACe
ISRO Registered Space Tutor
S7-SA2-0412
What is the Application of Matrices in Graph Theory (Adjacency Matrix)?
Grade Level:
Class 12
AI/ML, Physics, Biotechnology, FinTech, EVs, Space Technology, Climate Science, Blockchain, Medicine, Engineering, Law, Economics
Definition
What is it?
The application of matrices in graph theory, specifically using an Adjacency Matrix, helps us represent connections between different points (like cities or friends) in a structured way. An Adjacency Matrix is a square table (matrix) where rows and columns represent these points, and the numbers inside show if there's a direct path or connection between them.
Simple Example
Quick Example
Imagine your school friends. If you are friends with Rohan, and Rohan is friends with Priya, we can show these connections. An Adjacency Matrix would have rows and columns for each friend. A '1' would mean they are direct friends, and a '0' would mean they are not. This makes it easy to see all direct friendships at a glance.
Worked Example
Step-by-Step
Let's say we have three friends: Ayesha, Bala, and Chitra. Ayesha is friends with Bala. Bala is friends with Chitra. Chitra is friends with Ayesha. We want to create an Adjacency Matrix.
Step 1: List the friends (vertices): Ayesha (A), Bala (B), Chitra (C).
---
Step 2: Create a 3x3 matrix (since there are 3 friends). Label rows and columns with A, B, C.
A B C
A
B
C
---
Step 3: Fill in '1' if there's a direct friendship, '0' if not. Remember, a person is not friends with themselves (usually).
- Ayesha is friends with Bala: So, A to B is 1. (A,B) = 1.
- Bala is friends with Chitra: So, B to C is 1. (B,C) = 1.
- Chitra is friends with Ayesha: So, C to A is 1. (C,A) = 1.
---
Step 4: Since friendship is usually mutual, if A is friends with B, then B is friends with A. So, (B,A) = 1, (C,B) = 1, (A,C) = 1.
---
Step 5: Fill in '0' for no direct friendship, and '0' for self-connection (diagonal).
A B C
A [0 1 1]
B [1 0 1]
C [1 1 0]
Answer: The Adjacency Matrix is:
[[0, 1, 1],
[1, 0, 1],
[1, 1, 0]]
Why It Matters
Understanding Adjacency Matrices is crucial for fields like AI/ML to build social networks, for FinTech to model transaction flows, and for Space Technology to plan communication links between satellites. Engineers use them to design efficient circuits, and data scientists use them to analyze complex data connections, opening doors to careers in cutting-edge technology.
Common Mistakes
MISTAKE: Filling '1' for a path that requires multiple steps, not just a direct connection. | CORRECTION: An Adjacency Matrix only shows DIRECT connections. If you need to go from A to C via B, that's not a direct connection from A to C.
MISTAKE: Not making the matrix symmetric for undirected graphs (like friendships). | CORRECTION: If the connection goes both ways (e.g., if A is friends with B, then B is friends with A), then the entry (i,j) must be the same as (j,i).
MISTAKE: Forgetting to put '0's on the main diagonal (unless a node connects to itself). | CORRECTION: In most simple graphs, a node doesn't connect to itself directly. So, the entries where the row and column are the same (like A to A, B to B) should be 0.
Practice Questions
Try It Yourself
QUESTION: Draw an Adjacency Matrix for four cities: Delhi (D), Mumbai (M), Chennai (C), Kolkata (K). There are direct flights between: Delhi-Mumbai, Mumbai-Chennai, Chennai-Kolkata. | ANSWER:
D M C K
D [0 1 0 0]
M [1 0 1 0]
C [0 1 0 1]
K [0 0 1 0]
QUESTION: A small computer network has 4 computers: P, Q, R, S. P connects to Q and R. Q connects to R and S. R connects to S. Create the Adjacency Matrix. | ANSWER:
P Q R S
P [0 1 1 0]
Q [1 0 1 1]
R [1 1 0 1]
S [0 1 1 0]
QUESTION: Consider a directed graph (one-way street) with nodes 1, 2, 3. There's a path from 1 to 2, and from 2 to 3. There is also a path from 3 to 1. Create the Adjacency Matrix. (Hint: Direction matters, so (i,j) might not be the same as (j,i)). | ANSWER:
1 2 3
1 [0 1 0]
2 [0 0 1]
3 [1 0 0]
MCQ
Quick Quiz
What does a '1' at position (i, j) in an Adjacency Matrix represent?
There is no connection between node i and node j.
There is a direct connection between node i and node j.
There is a connection between node i and node j through another node.
Node i is the same as node j.
The Correct Answer Is:
B
A '1' in an Adjacency Matrix explicitly indicates a direct link or connection between the node represented by the row (i) and the node represented by the column (j). '0' would mean no direct connection, and multi-step connections are not shown directly.
Real World Connection
In the Real World
When you use Google Maps or Ola/Uber, the app uses similar matrix ideas to find the shortest route from your current location to your destination. Each road intersection is a 'node', and each road segment is a 'connection'. Adjacency matrices help these apps quickly calculate all possible paths and choose the most efficient one for your auto-rickshaw ride or bus journey.
Key Vocabulary
Key Terms
MATRIX: A rectangular arrangement of numbers in rows and columns. | GRAPH THEORY: The study of graphs, which are mathematical structures used to model pairwise relations between objects. | ADJACENCY MATRIX: A square matrix used to represent a finite graph. | NODE (VERTEX): A point or object in a graph. | EDGE: A connection between two nodes in a graph.
What's Next
What to Learn Next
Great job understanding Adjacency Matrices! Next, you should explore how to find paths of different lengths using matrix multiplication. This will help you discover not just direct connections, but also connections that require two, three, or more steps, which is super useful for understanding complex networks.
