Courses
Courses for Kids
Free study material
Offline Centres
More
Store Icon
Store
seo-qna
SearchIcon
banner

Incidence matrix and Adjacency matrix of a graph will always have the same dimensions?
a) True
b) False

Answer
VerifiedVerified
502.2k+ views
like imagedislike image
Hint: The size of the incidence matrix is equal to the number of vertices and the number of edges of the graph whereas the adjacency matrix depends on the labeling of vertices of the graph.

Complete step-by-step answer:
The Incidence Matrix of a Graph:
Let G=(V,E)be a graph where V={1,2,......,n} and E={e1,e2,....,em}. The incidence matrix of G is an n×m matrix B=(bik), where each row corresponds to a vertex and each column corresponds to an edge such that if ek is an edge between i and j, then all elements of column k are 0, except bik=bjk=1

The Adjacency Matrix of a Graph:
Let G=(V,E)be a graph where V={1,2,......,n} and E={e1,e2,....,em}. The incidence matrix of G is an n×m matrix A=aij, where aij=1 if there is an edge between vertex i and vertex j, else aij=0

Therefore, we conclude that the Incidence matrix and Adjacency matrix of a graph does not have the same dimensions.

So, the correct answer is “Option b”.

Note: An incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y.
An adjacency matrix is a square matrix utilized to describe a finite graph. The components of the matrix express whether the pairs of a finite set of vertices (also called nodes) are adjacent in the graph or not. Sometimes adjacency matrices are also called a vertex matrix.