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
\(= \left| {\left[ {{A_r}} \right]{{\left[ {{A_r}} \right]}^T}} \right|\) for just connected graph
Calculation:
Given incidence matrix is
\(A = \left[ {\begin{array}{*{20}{c}} { - 1}&0&1&1&{ - 1}&0\\ 1&{ - 1}&0&0&0&{ - 1}\\ 0&1&{ - 1}&{ - 1}&1&0 \end{array}} \right]\)
For the above matrix, the algebraic sum of elements of all the columns is not zero.
It is reduced incidence matrix.
\({A_r} = \left[ {\begin{array}{*{20}{c}} { - 1}&0&1&1&{ - 1}&0\\ 1&{ - 1}&0&0&0&{ - 1}\\ 0&1&{ - 1}&{ - 1}&1&0 \end{array}} \right]\)
\({\left[ {{A_r}} \right]^T} = \left[ {\begin{array}{*{20}{c}} { - 1}&1&0\\ 0&{ - 1}&1\\ 1&0&{ - 1}\\ 1&0&{ - 1}\\ { - 1}&0&1\\ 0&{ - 1}&0 \end{array}} \right]\)
\(\left[ {{A_r}} \right]{\left[ {{A_r}} \right]^T} = \left[ {\begin{array}{*{20}{c}} { - 1}&0&1&1&{ - 1}&0\\ 1&{ - 1}&0&0&0&{ - 1}\\ 0&1&{ - 1}&{ - 1}&1&0 \end{array}} \right]\left[ {\begin{array}{*{20}{c}} { - 1}&1&0\\ 0&{ - 1}&1\\ 1&0&{ - 1}\\ 1&0&{ - 1}\\ { - 1}&0&1\\ 0&{ - 1}&0 \end{array}} \right]\)
\(= \left[ {\begin{array}{*{20}{c}} 4&{ - 1}&{ - 3}\\ { - 1}&3&{ - 1}\\ { - 3}&{ - 1}&4 \end{array}} \right]\)
Number of trees \(= \left| {\left[ {{A_r}} \right]{{\left[ {{A_r}} \right]}^T}} \right|\)
\(= \left| {\begin{array}{*{20}{c}} 4&{ - 1}&{ - 3}\\ { - 1}&3&{ - 1}\\ { - 3}&{ - 1}&4 \end{array}} \right|\)
= 4 (12 – 1) + 1 (-4 – 3) – 3 (1 + 9)
= 44 – 7 – 30 = 7