Graph Theory - 1 - Free MCQ Practice Test with solutions, GATE EE Network

Concept:

• The no. of rows in an incident matrix determines the total no. of nodes present in a graph.
• The no. of columns in an incident matrix determines the total no. of branches present in a graph.
• The incoming arrow to a node is taken as -1.
• The outgoing arrow to a node is taken as +1.

Explanation:

Following are the results from the above incident matrix:

No. of rows = 4 = Total no. of nodes

No. of columns = 6 = Total no. of branches

Node 1: Three outgoing arrows

Node 2: Two incoming and one outgoing arrow

Node 3: One incoming and two outgoing arrows

Node 4: Three incoming arrows

All the above conditions are fulfilled by option 2.

Incidence matrix:

• It is the matrix that gives a relation between the branches and nodes.
• The rows of the incidence matrix [A] represent the number of nodes and the column of the matrix represents the number of branches in the given graph.
• If there are ‘n’ number of rows in a given incidence matrix[A], that means in a graph there are ‘n’ number of nodes. 
• Similarly, if there are ‘b’ number of columns in that given incidence matrix[A], that means in that graph there are ‘b’ number of branches.
• We can construct the incidence matrix for the directed graph. We can draw a graph with the help of the incidence matrix.
• The algebraic sum of elements of all the columns is zero.
• The rank of the incidence matrix is (n – 1).
• The determinant of the incidence matrix of a closed loop is zero.

Hence, Only statement I is correct.

Concept:

Network topology:

Network topology refers to the manner in which the links and nodes of a network are arranged to relate to each other.

Ring Topology:

 In a ring topology,each device a dedicated point-to-point line configuration only with the two device on either side of it. A signal is passed along the ring in one direction from devices to device,until it reaches its destination.

Hence the correct answer is ring.

Tie set matrix:

• It gives the relation between tie-set currents and branch currents.
• The rows of a matrix represent the tie-set currents.
• The columns of a matrix represent branches of the graph.
• The order of the tie set matrix is (B – N + 1) × b
• The rank of a tie-set matrix is (B – N + 1)

Cut-set matrix:

• It gives the relation between cut-set voltages and branch voltages.
• The rows of a matrix represent the cut-set voltages.
• The columns of a matrix represent the branches of the graph.
• The order of the cut-set matrix is (n – 1) × b.
• The rank of a cut-set matrix is (n – 1)

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 order of  incidence matrix will be (n × b).
• The determinant of the incidence matrix of a closed loop is zero.

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.

Duality:

• Two electrical networks are said to be dual networks if the mesh equations of one network are equal to the node equation of others.
• Identical behavior patterns observed between voltages and currents in two circuits illustrate the principle of duality.
• The dual networks are based on Kirchhoff Current Law and Kirchhoff Voltage Law.

Some important dual relations are given below.

Concept:

Tie set matrix:

• It gives the relation between tie-set currents and branch currents.
• The rows of a matrix represent the tie-set currents.
• The columns of a matrix represent branches of the graph.
• The order of the tie set matrix is (B – N + 1) × b
• The rank of a tie-set matrix is (B – N + 1)

Application:

Circuit Diagram:

The above figure consists of 4 Nodes and 6 Branches

B = 6, N = 4

The rows of a matrix represent the tie-set currents = (B - N + 1)

= 6 - 4 + 1

= 3

Concept:

The tree is a connected subgraph that consists of all the nodes of the network but it does not consist of any closed path. So, we have drawn below the trees possible without forming any loop.

On other hand, cutsets are the same as a twig(tree branches). 

Analysis:

Possible trees of the given graph is:

Therefore no. of trees possible P = 4.

Possible cut sets of the given graph are

No. of possible cut sets Q = 6

Concept:

Nodal Analysis:

Nodal analysis is a method of analyzing network with the help of KCL equations.

For a network of N nodes, the number of simultaneous equations to be solved to get the unknowns

= Number of KCL equations

= N - 1

Mesh Analysis:

Mesh analysis is a method of analyzing network with the help of KVL equations.

For a network having N nodes and B branches, the number of simultaneous equations to be solved to get the unknowns

= Number of KVL equations

= number of independent loop equations

= B - N + 1

Calculation:

Given that, number of loops (l) = 3

Number of branches (b) = 8

In any network, number of independent loops,

l = b – n + 1

⇒ 3 = 8 – n + 1

⇒ n = 6

Connected graph: A graph is said to be connected if there exists at least one path between any two vertices (nodes) of the network. On the other hand, if a graph contains at least two separate parts, then it is called an unconnected graph graph.

In a connected network of N > 2 nodes have at most one branch directly connecting any pair of nodes. The graph of the network must have at least N branches for one or more closed paths to be existing.

Tie set matrix:

• It gives the relation between tie-set currents and branch currents.
• The rows of a matrix represent the tie-set currents.
• The columns of a matrix represent branches of the graph.
• The order of the tie set matrix is (B – N + 1) × b
• The rank of a tie-set matrix is (B – N + 1)

Cut-set matrix:

• It gives the relation between cut-set voltages and branch voltages.
• The rows of a matrix represent the cut-set voltages.
• The columns of a matrix represent the branches of the graph.
• The order of the cut-set matrix is (n – 1) × b.
• The rank of a cut-set matrix is (n – 1)

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 order of  incidence matrix will be (n × b).
• The determinant of the incidence matrix of a closed loop is zero.

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.