All Exams Test series for 1 year @ ₹349 only
Question

Consider the following regarding circuit theory :

1. The algebraic sum of the row entries of an incidence matrix is zero.

 2. The determinant of the incidence matrix of a closed loop is zero. 

3. A fundamental tie-set of a graph with respect to a tree is a loop formed by only one link associated with other twigs.

Which of the above statements are correct?

The correct answer is
1 and 3 only

The question asks to evaluate three statements regarding circuit theory concepts like incidence matrices and graph theory properties.

Statement 1: Incidence Matrix Row Entries Sum

An incidence matrix $A$ ($N \times M$) represents the relationship between $N$ nodes and $M$ edges. For a directed graph, each column corresponds to an edge, and typically has one $+1$ (edge leaving a node) and one $-1$ (edge entering a node), summing to $0$. The sum of all entries across all rows and columns is:

$ \sum_{i=1}^{N} \sum_{j=1}^{M} a_{ij} = \sum_{j=1}^{M} \left( \sum_{i=1}^{N} a_{ij} \right) = \sum_{j=1}^{M} 0 = 0 $

This property holds true. Therefore, statement 1 is correct.

Statement 2: Closed Loop Incidence Matrix Determinant

Consider a closed loop, which is a cycle graph ($C_N$). If we use the *undirected* incidence matrix definition (where $a_{ij}=1$ if node $i$ is incident to edge $j$, and $0$ otherwise), the matrix is square ($N \times N$). For example, a triangle ($C_3$) has the incidence matrix:

$ A = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix} $

The determinant of this matrix is $1(1)-0+1(1) = 2$. Since the determinant is not always zero for an undirected incidence matrix of a closed loop, statement 2 is incorrect.

Statement 3: Fundamental Tie-Set Definition

A fundamental tie-set (or fundamental circuit) in graph theory is uniquely defined with respect to a chosen spanning tree. It consists of a single non-tree edge (a 'link') and the unique path of tree edges (twigs) that connects the endpoints of that link. This forms a simple loop within the graph.

Statement 3 accurately describes this definition. Therefore, statement 3 is correct.

Conclusion on Correct Statements

Based on the analysis, statements 1 and 3 are correct, while statement 2 is incorrect.

  • Statement 1: Correct
  • Statement 2: Incorrect
  • Statement 3: Correct

The correct option is the one that includes statements 1 and 3 only.

Was this answer helpful?

Important Questions from Graph Theory

  1. A principal node is a

  2. Which of the following statement(s) is/are correct regarding about the undirected graph?

    I. Number of odd degree vertices is even.

    II. Sum of degrees of all vertices is even.

  3. Let $G(V, E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u, v)$, $u, v \in V$ such that $u \neq v$, be 30. Let T be any breadth-first-search tree of G. Which ONE of the given options is CORRECT for every such graph G?

  4. Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge.
    Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in $G$ before and after the edge weight update?
  5. Maintaining a graph in memory by means of its adjacency matrix is known as
Need Expert Advice?

Start Your Preparation with Prepp Mobile App

Download the app from Google Play & App Store
Download the app from Google Play & App Store
Prepp Mobile App