67 views

Let  $G = (V, G)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed 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

1. $\Theta (\mid E \mid + \mid V \mid) \\$
2. $\Theta (\mid E \mid \mid V \mid) \\$
3. $\Theta(E \mid \log \mid V \mid) \\$
4. $\Theta( \mid V \mid)$