graph theory, incidance matrix, complete incidance matrix, reduced incidance matrix

 Graph Theory

Graph theory is the branch of mathematics dealing with graphs. In network analysis, graphs are used extensively to represent a network being analyzed. The graph of a network captures only certain aspects of a network; those aspects related to its connectivity, or, in other words, its topology.

Incidence matrix:

Any oriented graph can be described completely in a compact matrix form. Here we specify the orientation of each branch in the graph and the nodes at which this branch is incident. This branch is called incident matrix. When one row is completely deleted from the matrix the remaining matrix is called a reduced incidence matrix.

The rows of the matrix represent the nodes and the columns represent the branches of the graph.

i. The elements of the incidence matrix will be +1, -1 or zero.

ii. If a branch is connected to a node and its orientation is away from the node the corresponding element is marked +1.

iii. If a branch is connected to a node and its orientation is towards the node then the corresponding element is marked – 1.

iv. If a branch is not connected to a given node then the corresponding element is marked zero.

Incidance matrices are classified into two types.

1. Complete Incidence Matrix

2. Reduced Incidence Matrix

Complete incidence matrix:

An incidence matrix in which the summation of elements in any column is zero is called a complete incidence matrix.

 

It is an N × B matrix with elements of

 

An = [akj]

 

akj = 1, when the branch bj is incident to and oriented away from the kth node.

= −1, when the branch bj is incident to and oriented towards the kth node.

= 0, when the branch bj is not incident to the kth node. As each branch of the graph is incident to exactly two nodes,

n

Σ akj = 0

k=0

That is, each column of An has exactly two non zero elements, one being +1 and the other −1. Sum of elements of any column is zero. The columns of An are linearly dependent. The rank of the matrix is less than N.

Significance of the incidence matrix lies in the fact that it translates all the geometrical features in the graph into an algebraic expression.

Using the incidence matrix, we can write KCL as

An ∗ ib = 0,

Where ib =branch current vector.

But these equations are not linearly independent. The rank of the matrix An is N − 1. This property of An is used to define another matrix called reduced incidence matrix or bus incidence matrix.

Reduced incidence matrix:

The reduced incidence matrix is obtained from a complete incidence matrix by eliminating a row. Hence the summation of elements in any column is not zero.

Any node of a connected graph can be selected as a reference node. Then the voltages of the other nodes (referred to as buses) can be measured with respect to the assigned reference. The matrix obtained from An by deleting the row corresponding to the reference

 

node is the element bus incident matrix A and is called bus incidence matrix with dimension (N − 1) × B. A is rectangular and therefore singular.

From A, we have A ∗ ib = 0, which represents a set of linearly independent equations and there are N − 1 independent node equations.

For the graph shown in Fig 2.3(a), with d selected as the reference node, the reduced incidence matrix is