GATE-2024-CS1(Forenoon)
March 9, 2025UGC NET Dec-2020 and June-2021 Paper-2
March 9, 2025GATE 2022
|
Question 52
|
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
|
The diagonal entries of A 2 are the degrees of the vertices of the graph.
|
|
|
If the graph is connected, then none of the entries of A^ n + 1 + I n can be zero.
|
|
|
If the sum of all the elements of A is at most 2( n- 1), then the graph must be acyclic.
|
|
|
If there is at least a 1 in each of A ’s rows and columns, then the graph must be Connected.
|
Question 52 Explanation:
IF A is adjacency matrix, then in the matrix A*A = A^2 we have
The entries aii show the number of 2-length paths between the nodes i and j. Why this happens is easy to see: if there is an edge ij and an edge jk, then there will be a path ik through j. The entries ii are the degrees of the nodes i.
Similarly in A^3 we have the entries aii that show the number of 3-length paths between the nodes i and j.
In A^n-1 + I n, we will have at least n-1 length paths, so there is no possibility of zero entires
The entries aii show the number of 2-length paths between the nodes i and j. Why this happens is easy to see: if there is an edge ij and an edge jk, then there will be a path ik through j. The entries ii are the degrees of the nodes i.
Similarly in A^3 we have the entries aii that show the number of 3-length paths between the nodes i and j.
In A^n-1 + I n, we will have at least n-1 length paths, so there is no possibility of zero entires
Correct Answer: A
Question 52 Explanation:
IF A is adjacency matrix, then in the matrix A*A = A^2 we have
The entries aii show the number of 2-length paths between the nodes i and j. Why this happens is easy to see: if there is an edge ij and an edge jk, then there will be a path ik through j. The entries ii are the degrees of the nodes i.
Similarly in A^3 we have the entries aii that show the number of 3-length paths between the nodes i and j.
In A^n-1 + I n, we will have at least n-1 length paths, so there is no possibility of zero entires
The entries aii show the number of 2-length paths between the nodes i and j. Why this happens is easy to see: if there is an edge ij and an edge jk, then there will be a path ik through j. The entries ii are the degrees of the nodes i.
Similarly in A^3 we have the entries aii that show the number of 3-length paths between the nodes i and j.
In A^n-1 + I n, we will have at least n-1 length paths, so there is no possibility of zero entires