Incidence matrix:
- It is the matrix which gives relation between branches and nodes.
- The rows of matrix represent the number of nodes and the columns of matrix represents the numbers of branches.
- We can construct the incidence matrix for the directed graph. We can draw a graph with the help of incidence matrix.
- The algebraic sum of elements of all the columns is zero.
- The rank of incidence matrix is (n–1).
The elements of incidence matrix are given by [A] = [aij]n × b
Where aij = 1, if jth branch is incident at ith node and oriented away.
aij = -1, if jth branch is incident at ith node and oriented towards.
aij = 0, if jth branch is not incident at ith node
Reduced incidence matrix:
- If one of the nodes in the given graph is considered as reference node, then that row can be neglected by writing incidence matrix is called as reduced incidence matrix.
- The order of reduced incidence matrix is (n–1) × b.
- The Algebraic sum of some of the columns is not zero.
Number of trees of a graph can be calculate by using the following formula.
Number of trees = nn-2, n > 2 for completely connected graph
for just connected graph
Calculation:
Given incidence matrix is
For the above matrix, the algebraic sum of elements of all the columns is not zero.
It is reduced incidence matrix.
Number of trees
= 4 (12 – 1) + 1 (-4 – 3) – 3 (1 + 9)
= 44 – 7 – 30 = 7