GO Classes DPP | PYTHON & DSA |GRAPH

Answer 1

A. DIJKSTRA'S ALGORITHM CAN BE USED...: INCORRECT.
Dijkstra's algorithm fails with negative edge weights because it cannot "correct" the distance to a node once it has been processed. Bellman-Ford or Floyd-Warshall would be required instead.

B. THE MINIMUM NUMBER OF EDGES IS $n-k$ : CORRECT. To minimize edges, each component must be a tree. Since a tree with $v$ vertices has $v-1$ edges, the sum for $k$ components is $\sum\left(v_i-1\right)=\left(\sum v_i\right)-k=n-k$.

C. THE GRAPH MUST CONTAIN A CYCLE IF THE NUMBER OF EDGES IS $n$ : CORRECT.

For a graph with $n$ vertices, the maximum number of edges it can have without a cycle (i.e., being a forest) is $n-1$. If the number of edges reaches $n$, at least one cycle is mathematically guaranteed

D. THE MAXIMUM NUMBER OF EDGES IS $\frac{(n-k)(n-k+1)}{2}$ : CORRECT. To maximize edges in a graph with $k$ components, you minimize the vertices in $k-1$ components ( 1 vertex each) and put all remaining $n-(k-1)$ vertices into one component. This component is a complete graph $\left(K_{n-k+1}\right)$. The number of edges is $\binom{n-k+1}{2}=\frac{(n-k+1)(n-k)}{2}$.