Question:
Let \( A \) be the adjacency matrix of a simple undirected graph \( G \). Suppose \( A \) is its own inverse. Which one of the following statements is always TRUE?
Let \( A \) be the adjacency matrix of a simple undirected graph \( G \). Suppose \( A \) is its own inverse. Which one of the following statements is always TRUE?
Show Hint
When the adjacency matrix of a graph satisfies \( A \cdot A = I \), the graph represents a perfect matching.
Updated On: Jan 23, 2025
- \( G \) is a cycle
- \( G \) is a perfect matching
- \( G \) is a complete graph
- There is no such graph \( G \)
Hide Solution
Verified By Collegedunia
The Correct Option is B
Solution and Explanation
If \( A \) is the adjacency matrix of an undirected graph \( G \), and \( A \cdot A = I \) (where \( I \) is the identity matrix), it means that the graph \( G \) satisfies the following conditions:
1. Each node in \( G \) is connected to exactly one other node because \( A \cdot A = I \) implies no node connects back to itself (diagonal is 1 in \( I \)).
2. There are no paths of length 2 between any two nodes in \( G \).
This describes a perfect matching, where each node is paired with exactly one other node.
Step 1: Analyze other options.
(A) \( G \) is a cycle: A cycle would not satisfy \( A \cdot A = I \) because there are paths of length 2.
(C) \( G \) is a complete graph: A complete graph does not satisfy \( A \cdot A = I \) because all nodes are connected.
(D) There is no such graph \( G \): This is incorrect because graphs with perfect matchings exist.
Final Answer:
\[
\boxed{\text{Perfect Matching}}
\]
Was this answer helpful?
0
0
Top Questions on Data Interpretation
- In a class of 40 students, the ratio of boys to girls is 3:2. The average marks scored by boys is 42, and that by girls is 46. What is the average marks scored by the whole class?
- CUET (UG) - 2024
- General Aptitude
- Data Interpretation
- The monthly salary for a person who follows the same expense pattern, but has a petrol expense of Rs 500 p.m., is:
- VITEEE - 2024
- General Aptitude
- Data Interpretation
- Let \(P\) be the partial order defined on the set \(\{1, 2, 3, 4\}\) as follows: \[ P = \{(x, x) \mid x \in \{1, 2, 3, 4\}\} \cup \{(1, 2), (3, 2), (3, 4)\} \] The number of total orders on \(\{1, 2, 3, 4\}\) that contain \(P\) is ...........\_\_\_.
- GATE CS - 2024
- General Aptitude
- Data Interpretation
- When six unbiased dice are rolled simultaneously, the probability of getting all distinct numbers (i.e., \( 1, 2, 3, 4, 5, \) and \( 6 \)) is
- GATE CS - 2024
- General Aptitude
- Data Interpretation
- Consider a system that uses 5 bits for representing signed integers in 2’s complement format. In this system, two integers \( A \) and \( B \) are represented as \( A = 01010 \) and \( B = 11010 \). Which one of the following operations will result in either an arithmetic overflow or an arithmetic underflow?
- GATE CS - 2024
- General Aptitude
- Data Interpretation
View More Questions
Questions Asked in GATE CS exam
Which of the following is the greatest? \[ 0.6, \ 0.666, \ \frac{5}{6}, \ \frac{2}{3} \]
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);What is the output of the following C code?
void foo(int *p, int x) { *p = x; } void main() { int *z; int a = 20, b = 25; z = a; // Incorrect: Should be z = a; foo(z, b); printf("%d", a); }Issue: The statement
z = a;is invalid becauseais an integer, andzis a pointer.Find the signed binary expansion of the number -6.
Match the following layers with their corresponding functionalities:
\[ \begin{array}{|c|c|} \hline \textbf{Layer} & \textbf{Functionality} \\ \hline \text{Networking Layer} & \text{Data packet transfer} \\ \text{Transport Layer} & \text{Host-to-host communication} \\ \text{Data Link Layer} & \text{Error detection and correction} \\ \hline \end{array} \]- GATE CS - 2025
- Programming in C
View More Questions