سوال ۵۸ کنکور ارشد مهندسی کامپیوتر ۱۴۰۳

Check each statement on a connected weighted graph $G=(V,E)$. Connectivity guarantees $|E|\ge |V|-1$, so $|V|=O(|E|)$ and $O(|V|+|E|)=O(|E|)$.

Statement 1 — TRUE. When every edge has the same weight, every spanning tree has the same total weight, so any spanning tree is a minimum spanning tree. A spanning tree of a connected graph is produced by a single BFS or DFS in $O(|V|+|E|)$, which equals $O(|E|)$ here. No heap or sorting is needed.

Statement 2 — TRUE. A cycle in a directed graph is detected by a single DFS: a back edge to a vertex currently on the recursion stack (gray vertex) signals a cycle. DFS runs in $\Theta(|V|+|E|)$.

Statement 3 — TRUE. If all edge weights are pairwise distinct, the minimum spanning tree is unique. Both Prim and Kruskal are correct MST algorithms, so each returns this same unique tree. (The MST can fail to be unique only when ties among edge weights exist.)

Statement 4 — TRUE. Kruskal's algorithm costs $O(E\log E)=O(E\log V)$ (dominated by sorting the edges). Prim's algorithm with a Fibonacci heap costs $O(E + V\log V)$, and with a binary heap $O(E\log V)$. Since $O(E + V\log V)\subseteq O(E\log V),$ Prim (Fibonacci-heap version) is never asymptotically worse than Kruskal — and is strictly better on dense graphs. So an implementation of Prim meeting the claim exists.

All four statements are correct, so the count is $4$, which is option 4.

Exam trick: "Pairwise-distinct edge weights $\Rightarrow$ unique MST" is the key fact behind statement 3; ties are the only source of multiple MSTs. And remember Prim-with-Fibonacci-heap $O(E+V\log V)$ matches or beats Kruskal's $O(E\log V)$.