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?
Statement Analysis for Graph Theory Concepts
Statement 1 Analysis: Chord Definition
Statement 1 defines a chord as "that branch of the graph that does not belong to the particular tree."
Reasoning: In graph theory and network analysis, edges are commonly referred to as branches. A chord is an edge belonging to the original graph that is not part of a specific spanning tree chosen for analysis. However, if the term "branch" is strictly interpreted as exclusively meaning a "tree branch" (an edge within the spanning tree), then a chord, by definition being a non-tree edge, cannot be a "branch of the tree". This interpretation makes the statement technically incorrect due to terminological ambiguity.
Statement 2 Analysis: Cut-set Definition
Statement 2 defines a cut-set relative to a tree as a set containing "one chord and all of the free branches contained in the free path formed between two vertices of the chord."
Reasoning: This definition deviates from the standard concept of a fundamental cut-set in graph theory. A fundamental cut-set is typically associated with removing a single *tree branch* from the spanning tree. The cut-set includes this removed tree branch and *all* chords (non-tree edges) that connect the two components formed by removing the tree branch. The statement's description is inaccurate.
Statement 3 Analysis: Network Variables
Statement 3 posits that the minimum number of variables for network analysis is $M + N - 1$, where $M$ is the number of branches and $N$ is the number of nodes.
Reasoning: Network analysis often utilizes concepts like fundamental cycles or fundamental cut-sets. For a connected graph:
- The number of fundamental cycles is $M - N + 1$. This often corresponds to the number of mesh currents needed in mesh analysis.
- The number of fundamental cut-sets is $N - 1$. This often corresponds to the number of node voltages needed in nodal analysis.
The formula $M + N - 1$ does not represent a standard basis size for network analysis variables. Hence, the statement is incorrect.
Conclusion on Incorrect Statements
The analysis reveals that:
- Statement 1 is considered incorrect due to a strict interpretation of the term "branch".
- Statement 2 provides an incorrect definition of a cut-set.
- Statement 3 uses an incorrect formula for the minimum number of network variables.
Therefore, statements 1, 2, and 3 are all not correct.
Final Answer: The final answer is D
Important Questions from Graph Theory
A principal node is a
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.
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?
- 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? - Maintaining a graph in memory by means of its adjacency matrix is known as
