What is an Adjacency Matrix?

S3-SA5-0377

Grade Level:

Class 10

AI/ML, Data Science, Physics, Economics, Cryptography, Computer Science, Engineering

Definition

What is it?

An Adjacency Matrix is a square table (like a grid) that shows connections between different points or 'nodes' in a network. It uses numbers (usually 0s and 1s) to tell us if one point is directly linked to another. Think of it as a map that uses numbers to show which cities have direct roads between them.

Simple Example

Quick Example

Imagine 3 friends: Priya, Rohan, and Simran. Priya calls Rohan, and Rohan calls Simran. To make an adjacency matrix, we'd have a 3x3 grid. If Priya can call Rohan, we put a '1' where Priya meets Rohan. If Priya cannot call Simran directly, we put a '0'.

Worked Example

Step-by-Step

Let's say we have 4 cities: Delhi (D), Mumbai (M), Kolkata (K), Chennai (C).

---Step 1: Draw a table with cities as rows and columns. D M K C on top, and D M K C on the side.

---Step 2: Note direct flights: Delhi to Mumbai, Mumbai to Kolkata, Kolkata to Chennai, Chennai to Delhi. Also, Mumbai to Delhi (return flight) and Kolkata to Mumbai (return flight).

---Step 3: Fill in '1' if there's a direct flight from the row city to the column city, and '0' if there isn't.

---Step 4: For Delhi (row) to Mumbai (column), put 1. For Mumbai (row) to Delhi (column), put 1.

---Step 5: For Mumbai (row) to Kolkata (column), put 1. For Kolkata (row) to Mumbai (column), put 1.

---Step 6: For Kolkata (row) to Chennai (column), put 1. For Chennai (row) to Delhi (column), put 1.

---Step 7: All other cells where there's no direct flight (like Delhi to Kolkata, or Delhi to Chennai) get a '0'. A city does not have a flight to itself, so the diagonal (D to D, M to M, etc.) will be 0s unless specified otherwise.

---Answer: The Adjacency Matrix would look like this:
D M K C
D [0 1 0 0]
M [1 0 1 0]
K [0 1 0 1]
C [1 0 0 0]

Why It Matters

Adjacency matrices are super important for understanding how things are connected, like friends on social media or parts of a computer network. They help engineers design efficient systems, data scientists analyze relationships, and even power the 'people you may know' feature on apps. Learning this helps you think like a computer scientist or an AI developer!

Common Mistakes

MISTAKE: Filling a '1' for an indirect connection (e.g., A to B, B to C, but filling A to C as 1) | CORRECTION: An adjacency matrix only records DIRECT connections. If A connects to C only through B, then A to C should be '0'.

MISTAKE: Not understanding if the matrix is 'directed' or 'undirected' (e.g., if A connects to B, assuming B connects to A). | CORRECTION: If a connection is one-way (like a train from Delhi to Agra but no direct return), then only A to B gets a '1', not B to A. If it's two-way (like a road), then both A to B and B to A get '1'. Pay attention to the problem description.

MISTAKE: Confusing rows and columns, leading to incorrect placement of 0s and 1s. | CORRECTION: Always be consistent. If rows represent 'from' and columns represent 'to', stick to that convention throughout the matrix.

Practice Questions

Try It Yourself

QUESTION: Draw an Adjacency Matrix for 3 cities, A, B, C, where A is connected to B, and B is connected to C. All connections are two-way. | ANSWER:
A B C
A [0 1 0]
B [1 0 1]
C [0 1 0]

QUESTION: A social network has 4 users: P, Q, R, S. P follows Q. Q follows R. R follows P. S follows Q. Draw the Adjacency Matrix assuming 'follows' is a one-way connection. | ANSWER:
P Q R S
P [0 1 0 0]
Q [0 0 1 0]
R [1 0 0 0]
S [0 1 0 0]

QUESTION: Consider a small metro map with stations 1, 2, 3, 4, 5. Lines are: 1-2, 2-3, 3-4, 4-5. All lines are two-way. Also, there's a direct express line from 1 to 4. Create the Adjacency Matrix. | ANSWER:
1 2 3 4 5
1 [0 1 0 1 0]
2 [1 0 1 0 0]
3 [0 1 0 1 0]
4 [1 0 1 0 1]
5 [0 0 0 1 0]

MCQ

Quick Quiz

What does a '0' in an Adjacency Matrix usually represent?

A strong connection

A direct connection exists

No direct connection exists

A self-loop

The Correct Answer Is:

A '0' in an adjacency matrix indicates that there is no direct link or relationship between the two corresponding nodes. A '1' indicates a direct connection.

Real World Connection

In the Real World

Adjacency matrices are used by apps like Google Maps or Ola Cabs to figure out the shortest routes. Each city or junction is a 'node', and roads are 'connections'. The matrix helps them quickly see which junctions are directly linked and calculate travel times, helping your auto-rickshaw driver find the fastest way to your destination.

Key Vocabulary

Key Terms

NODE: A point or vertex in a network, like a city or a person | EDGE: A connection or link between two nodes, like a road or a friendship | DIRECTED GRAPH: A network where connections have a specific direction (one-way) | UNDIRECTED GRAPH: A network where connections are two-way | MATRIX: A rectangular array of numbers arranged in rows and columns

What's Next

What to Learn Next

Now that you understand adjacency matrices, you can explore 'Graph Theory'. This field uses these matrices to solve complex problems in computer science and engineering, helping you build a strong foundation for future studies.