Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d_1(u, v)$ and $d_2(u, v)$ be the shortest distances between $u$ and $v$ in $G$ and $T$, respectively. Which ONE of the options is CORRECT for all possible $G, T, u$ and $v$ ?
Let G be a connected undirected weighted graph. Consider the following two statements.
S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.
S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree. Which one of the following options is correct?
Consider the following table :
| Algorithms | Design Paradigms |
|---|---|
| (P) Kruskal | (ii) Greedy |
| (Q) Quicksort | (i) Divide and Conquer |
| (R) Floyd–Warshall | (iii) Dynamic Programming |
Match the algorithms to the design paradigms they are based on.
$$P:$$ Minimum spanning tree of $$G$$ does not change
$$Q:$$ Shortest path between any pair of vertices does not change