GATE CSE 2024 Set 2 | Greedy Method Question 1 | Algorithms

GATE CSE 2024 Set 2

MCQ (More than One Correct Answer)

-0.66

Let $G$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $G$ has even weight. Which of the following statements is/are TRUE for every such graph $G$?

All edges in $G$ have even weight

All edges in $G$ have even weight OR all edges in $G$ have odd weight

In each cycle $C$ in $G$, all edges in $C$ have even weight

In each cycle $C$ in $G$, either all edges in $C$ have even weight OR all edges in $C$ have odd weight

GATE CSE 2024 Set 2

Numerical

-0.66

The number of distinct minimum-weight spanning trees of the following graph is ________

GATE CSE 2024 Set 2 Algorithms - Greedy Method Question 1 English

Your input ____

GATE CSE 2020

MCQ (Single Correct Answer)

-0.67

Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u, v) $$ \in $$ V $$ \times $$ V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

$$\Theta \left( {\left| E \right| + \left| V \right|} \right)$$

$$\Theta \left( {\left| E \right|\left| V \right|} \right)$$

$$\Theta \left( {\left| E \right|\log \left| V \right|} \right)$$

$$\Theta \left( {\left| V \right|} \right)$$

GATE CSE 2020

Numerical

-0.67

Consider a graph G = (V, E), where V = {v₁, v₂, ...., v₁₀₀},
E = {(v_i, v_j) | 1 ≤ i < j ≤ 100}, and weight of the edge (v_i, v_j) is |i - j|. The weight of the minimum spanning tree of G is ______.

Your input ____