Let \( G \) be a simple, unweighted, and undirected graph. A subset of the vertices and edges of \( G \) are shown below.
It is given that \( a - b - c - d \) is a shortest path between \( a \) and \( d \); \( e - f - g - h \) is a shortest path between \( e \) and \( h \); \( a - f - c - h \) is a shortest path between \( a \) and \( h \). Which of the following is/are NOT the edges of \( G \)?
Let \( G \) be a simple, unweighted, and undirected graph. A subset of the vertices and edges of \( G \) are shown below.
It is given that \( a - b - c - d \) is a shortest path between \( a \) and \( d \); \( e - f - g - h \) is a shortest path between \( e \) and \( h \); \( a - f - c - h \) is a shortest path between \( a \) and \( h \). Which of the following is/are NOT the edges of \( G \)?
Show Hint
- \( (b,d) \)
- \( (b,g) \)
- \( (b,h) \)
- \( (e,g) \)
The Correct Option is A, C, D
Solution and Explanation
The shortest path from \( a \) to \( d \) is \( a - b - c - d \). This means there is no direct edge between \( b \) and \( d \).
The shortest path from \( e \) to \( h \) is \( e - f - g - h \). This implies that \( e \) and \( g \) are not directly connected.
The shortest path from \( a \) to \( h \) is \( a - f - c - h \), suggesting that \( b \) and \( h \) are not directly connected.
Top Questions on Graph Theory
Match LIST-I with LIST-II
Choose the correct answer from the options given below:
- CUET (PG) - 2025
- Data Science
- Graph Theory
Suppose a minimum spanning tree is to be generated for a graph whose edge weights are given below. Identify the graph which represents a valid minimum spanning tree?
\[\begin{array}{|c|c|}\hline \text{Edges through Vertex points} & \text{Weight of the corresponding Edge} \\ \hline (1,2) & 11 \\ \hline (3,6) & 14 \\ \hline (4,6) & 21 \\ \hline (2,6) & 24 \\ \hline (1,4) & 31 \\ \hline (3,5) & 36 \\ \hline \end{array}\]
Choose the correct answer from the options given below:
- CUET (PG) - 2025
- Data Science
- Graph Theory
- A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, \( n \) is _______.
- Dijkstra's algorithm fails for graphs with _______.
- Assume G is a simple undirected graph and some vertices of G are of odd degree. Add a node \( v \) to G and make it adjacent to each odd degree vertex of G, then the resultant graph is sure to be _______.
Questions Asked in GATE DA exam
Consider the following Python code snippet.
def f(a, b): if (a == 0): return b if (a % 2 == 1): return 2 * f((a - 1) / 2, b) return b + f(a - 1, b) print(f(15, 10))The value printed by the code snippet is 160 (Answer in integer).
- GATE DA - 2025
- Recursion
Consider the following tables, Loan and Borrower, of a bank.
Query: \[ \pi_{\text{branchname}, \text{customername}} (\text{Loan} \bowtie \text{Borrower}) \div \pi_{\text{branchname}}(\text{Loan}) \] where \( \bowtie \) denotes natural join. The number of tuples returned by the above relational algebra query is (Answer in integer).- GATE DA - 2025
- Relational Algebra
- Let \( D = \{ x^{(1)}, x^{(2)}, \dots, x^{(n)} \} \) be a dataset of \( n \) observations where each \( x^{(i)} \in \mathbb{R}^{100} \). It is given that \[ \sum_{i=1}^{n} x^{(i)} = 0. \] The covariance matrix computed from \( D \) has eigenvalues \( \lambda_i = 100^2 - i \), for \( 1 \leq i \leq 100 \). Let \( u \in \mathbb{R}^{100} \) be the direction of maximum variance with \( u^T u = 1 \). The value of \[ \frac{1}{n} \sum_{i=1}^{n} \left( u^T x^{(i)} \right)^2 = \underline{\hspace{2cm}} \quad \text{(Answer in integer)} \]
- GATE DA - 2025
- Matrix algebra
- The naive Bayes classifier is used to solve a two-class classification problem with class-labels \( y_1, y_2 \). Suppose the prior probabilities are \( P(y_1) = \frac{1}{3} \) and \( P(y_2) = \frac{2}{3} \). Assuming a discrete feature space with \[ P(x | y_1) = \frac{3}{4} \quad \text{and} \quad P(x | y_2) = \frac{1}{4} \] for a specific feature vector \( x \). The probability of misclassifying \( x \) is: (Round off to two decimal places)
- GATE DA - 2025
- Machine Learning
- Given data \( \{(-1, 1), (2, -5), (3, 5)\} \) of the form \( (x, y) \), we fit a model \( y = wx \) using linear least-squares regression. The optimal value of \( w \) is:
(Round off to three decimal places)- GATE DA - 2025
- Linear Algebra