Incidance Matrix, Tieset Matrix, Cut set Matrix

Incidance Matrix

 It is denoted by 'A'. Incidence matrix is that matrix which represents the graph such that with the help of that matrix we can draw a graph. This matrix can be denoted as [AC] As in every matrix, there are also rows and columns in incidence matrix [AC]. The rows of the matrix [AC] represent the number of nodes and the column of the matrix [AC] represent the number of branches in the given graph. If there are ‘n’ number of rows in a given incidence matrix, that means in a graph there are ‘n’ number of nodes. Similarly, if there are ‘m’ number of columns in that given incidence matrix, that means in that graph there are ‘m’ number of branches. Steps to Construct Incidence Matrix Following are the steps to draw the incidence matrix :- If a given kth node has outgoing branch, then we will write +1. If a given kth node has incoming branch, then we will write -1. Rest other branches will be considered 0. The rank of complete incidence matrix is (n-1), where n is the number of nodes of the graph. The order of incidence matrix is (n × b), where b is the number of branches of graph. From a given reduced incidence matrix we can draw complete incidence matrix by simply adding either +1, 0, or -1 on the condition that sum of each column should be zero.

Properties of Incidence Matrix A

Following properties are some of the simple conclusions from incidence matrix A.

Each column representing a branch contains two non-zero entries + 1 and —1; the rest being zero. The unit entries in a column identify the nodes of the branch between which it is connected.

The unit entries in a row identify the branches incident at a node. Their number is called the degree of the node.

A degree of 1 for a row means that there is one branch incident at the node. This is commonly possible in a tree.

If the degree of a node is two, then it indicates that two branches are incident at the node and these are in series.

Columns of A with unit entries in two identical rows correspond to two branches with same end nodes and hence they are in parallel.

Given the incidence matrix A the corresponding graph can be easily constructed since A is a complete mathematical replica of the graph.

If one row of A is deleted the resulting (n — 1) x b matrix is called the reduced incidence matrix A1. Given A1, A is easily obtained by using the first property.