Graph Theory

Graph Theory

When all the elements in a circuit or network are replaced by lines with dots, such configuration is called graph of the network. The all elements such as capacitor, inductor or resistor must satisfy Kirchhoff’s laws. Based on these laws, we can form a number of equations in graph theory.

Terminology Used in Graph Theory

1.     Node

A node is a point where branch is connected.

Examples

In following example we will find number of nodes.

Example 1.

graph theory node

In above diagrams, there are three nodes

Example 2

graph theory example of node

In above diagram, there are two number of nodes.

2.   Branch  

A branch is a line segment connected between two pair of nodes.

Number of branches in a network = n – 1

Example

graph theory example of branch

In above figure, there are four numbers of branches.

3.     Tree

A tree is a connected sub-graph of a network which includes all the nodes but no closed path. The graph of a network may have a number of trees.

4.     Co-Tree

The certain branches are removed to form tree, this removed branches are called links. The set of all links of a given tree is called the co-tree of the graph.

5.     Twigs

The branches of the tree are called, its twigs. The number of twigs on a tree is always one less than the number of nodes.

Twigs = nodes – 1

6.     Planar and Non-Planar Graphs

Planar graph are drawn on a plane surface where no two branches cross each other. Whereas, non-planar graph are those graph that can not be drawn on a plane surface without a crossover.

What is incidence matrix?

Incidence matrix shows which branch is incident to which node.

graph theory example of incident matrix

Arrows indicated in the branches of a graph result in an oriented or a directed graph. These arrows shows the flow of current or voltage rise in the network.

graph theory example of incident matrix with matrix

Properties of incidence matrix [Ai]

i)                   Algebraic sum of the column entries of an incidence matrix is zero.

ii)                 Determinant of the incidence matrix of a closed loop is zero.

iii)               The rank of a complete incidence matrix of a graph is n-1.

 

Leave a Reply

Your email address will not be published. Required fields are marked *