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 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.
Important Questions from Graph Theory
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?
- Maintaining a graph in memory by means of its adjacency matrix is known as
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on plane is equal to_________.
- The number of possible rooted trees in a phylogeny of three species is ________.
Consider the following statements regarding graph theory :
1. Chord is that branch of the graph that does not belong to the particular tree.
2. Cut-set is a unique set with respect to a given tree of a connected graph containing one chord and all of the free branches contained in the free path formed between two vertices of the chord.
3. If M represents the number of branches and N the number of nodes, the minimum number of variables involved in analyzing a network is equal to $(M + N − 1)$.
Which of the above statements are not correct?
