Exams › GATE › Technical
Let `w` be the minimum weight among all edge weights in an undirected connected graph. Let `e` be a specific edge of weight `w`. Which of the following is false?
- There is a minimum spanning tree containing `e`.
- If `e` is not in a minimum spanning tree `T`, then in the cycle formed by adding `e` to `T`, all edges have the same weight.
- Every minimum spanning tree has an edge of weight `w`.
- `e` is present in every minimum spanning tree.
Correct answer: `e` is present in every minimum spanning tree.
Solution
A minimum-weight edge belongs to at least one minimum spanning tree by the cut property. However, it need not appear in every MST if there are multiple minimum-weight edges or alternative equal-weight choices. Therefore, the statement claiming it is present in every MST is false.
Related GATE Technical questions
- Given an integer array of size \(N\), we want to check whether the array is sorted in either ascending or descending order. An algorithm solves this problem by making a single pass through the array and comparing each element only with its adjacent elements. The worst-case time complexity of this algorithm is
- 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)$, for $u,v \in V$ with $u \ne 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$?
- Which of the following sorting algorithms has the lowest worst-case complexity?
- Consider the following segment of C code: ```c int j, n; j = 1; while (j <= n) j = j * 2; ``` The number of comparisons made in the execution of the loop for any $n>0$ is:
- An array of `n` numbers is given, where `n` is even. The maximum as well as the minimum of these `n` numbers needs to be determined. Which of the following is true about the number of comparisons needed?
- Consider the following C code segment: ```c int IsPrime(n) { int i, n; for (i = 2; i <= sqrt(n); i++) if (n % i == 0) { printf("Not Prime\n"); return 0; } return 1; } ``` Let `T(n)` denote the number of times the `for` loop is executed by the program on input `n`. Which of the following is true?
⚔️ Practice GATE Technical free + battle 1v1 →