This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Adjacency Matrix”.

**1. In the given connected graph G, what is the value of rad(G) and diam(G)?****A) 2, 3**

B) 3, 2

C) 2, 2

D) 3, 3

Explanation: Value of eccentricity for vertices A, C is 2 whereas for F, B, D, E it is 3.

**2. Which of these adjacency matrices represents a simple graph?**

A) [ [1, 0, 0], [0, 1, 0], [0, 1, 1] ]

B) [ [1, 1, 1], [1, 1, 1], [1, 1, 1] ]

C) [ [0, 0, 1], [0, 0, 0], [0, 0, 1] ]**D) [ [0, 0, 1], [1, 0, 1], [1, 0, 0] ]**

Explanation: No-self loops are needed in a simple graph, and it should be undirected.

**3. Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], The total no. of ways in which every vertex can walk to itself using 2 edges is ________**

A) 2

B) 4**C) 6**

D) 8

Explanation: A^{2} = [ [2, 1, 1], [1, 2, 1], [1, 1, 2] ], all the 3 vertices can reach to themselves in 2 ways, hence a total of 3*2, 6 ways.

**4. If A[x+3][y+5] represents an adjacency matrix, which of these could be the value of x and y.****A) x=5, y=3**

B) x=3, y=5

C) x=3, y=3

D) x=5, y=5

Explanation: Square matrices make up all adjacency matrices.

**5. Two directed graphs(G and H) are isomorphic if and only if A=PBP-1, where P and A are adjacency matrices of G and H respectively.A) True**

B) False

Explanation: Isomorphic graphs have this property.

**6. Given the following program, what will be the 3rd number that’d get printed in the output sequence for the given input?**

#include <bits/stdc++.h> using namespace std; int cur=0; int G[10][10]; bool visited[10]; deque <int> q; void fun(int n); int main() { int num=0; int n; cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>G[i][j]; for(int i=0;i<n;i++) visited[i]=false; fun(n); return 0; } void fun(int n) { cout<<cur<<" "; visited[cur]=true; q.push_back(cur); do { for(int j=0;j<n;j++) { if(G[cur][j]==1 && !visited[j]) { q.push_back(j); cout<<j<<" "; visited[j]=true; } } q.pop_front(); if(!q.empty()) cur=q.front(); }while(!q.empty()); }

Input Sequence:-

9 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0

A) 2

B) 6**C) 8**

D) 4

Explanation: The given code performs the breadth first search routine on the Graph.

The sequence obtained would be 0 1 8 2 6 3 4 5 7.

**7. For which type of graph, the given program won’t run infinitely? The Input would be in the form of an adjacency Matrix and n is its dimension (1<n<10).**

#include <bits/stdc++.h> using namespace std; int G[10][10]; void fun(int n); int main() { int num=0; int n; cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>G[i][j]; fun(n); return 0; } void fun(int n) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(G[i][j]==1) j--; }

A) All Fully Connected Graphs**B) All Empty Graphs**

C) All Bipartite Graphs

D) All simple graphs

Explanation: The condition G[i][j]==1 will hold true for any graph (except an empty graph) with edges, resulting in an infinite loop.

**8. Given the following adjacency matrix of a graph(G) determine the number of components in the G.**

[0 1 1 0 0 0], [1 0 1 0 0 0], [1 1 0 0 0 0], [0 0 0 0 1 0], [0 0 0 1 0 0], [0 0 0 0 0 0].

A) 1

B) 2**C) 3**

D) 4

Explanation: The vertices 0th, 1st, and 2nd form a node, the 3rd and 4th form another, and the 5th vertex forms a component of a single vertex.

**9. What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?**

A) (n*(n-1))/2

B) (n*(n+1))/2**C) n*(n-1)**

D) n*(n+1)

Explanation: A simple graph’s diagonal values will always be zero out of n*n possible values.

**10. On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?**

A) Depends on the number of edges

B) Depends on the number of vertices**C) Is independent of both the number of edges and vertices**

D) It depends on both the number of edges and vertices

Explanation: It’s enough to see if the value of A[i][j] is 1 or 0, where A is the adjacency matrix, to see if there’s an edge between vertices I and j.

**11. Adjacency matrix of all graphs are symmetric.****A) False**

B) True

Explanation: Symmetric adjacency matrices are only generated by undirected graphs.

**12. The time complexity to calculate the number of edges in a graph whose information in stored in form of an adjacency matrix is ____________**

A) O(V)

B) O(E^{2})

C) O(E)**D) O(V ^{2})**

Explanation: As V entries are 0, a total of V

^{2}-V entries are to be examined.

**13. For the adjacency matrix of a directed graph the row sum is the _________ degree and the column sum is the ________ degree.**

A) in, out**B) out, in**

C) in, total

D) total, out

Explanation: The tail of the edge is represented by the row number of the matrix, while the head of the edge is represented by the column number.

**14. The number of elements in the adjacency matrix of a graph having 7 vertices is __________**

A) 7

B) 14

C) 36**D) 49**

Explanation: The adjacency matrix of a graph with n vertices has n*n components.

15. What would be the number of zeros in the adjacency matrix of the given graph?

A) 10**B) 6**

C) 16

D) 0

Explanation: The matrix has a total of 4*4=16 entries, with 6 of them being non-zero.

A square matrix is used to describe a finite graph as an adjacency matrix. The matrix’s elements show whether two vertices in the graph are adjacent or not. The adjacency matrix is a (0,1)-matrix with zeros on its diagonal in the special case of a finite simple graph. The adjacency matrix is symmetric if the graph is undirected (i.e. all of its edges are bidirectional). In spectral graph theory, the relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is investigated.