سوال ۶۲ کنکور ارشد مهندسی کامپیوتر ۱۴۰۱

The decisive property is that $G$ is planar. A simple planar graph on $n$ vertices has at most $m \le 3n-6$ edges, so its number of edges is $\Theta(n)$, not $\Theta(n^{2})$.

The phrase "you need not use the well-known MST algorithms" is the key hint: the generic comparison-based bounds (Kruskal/Prim give $\Theta(m\log n)=\Theta(n\log n)$ for a planar graph) are not the best achievable here. Planarity lets us do better.

Borůvka contraction on planar graphs. Run Borůvka's algorithm:

• In each phase every vertex selects its minimum-weight incident edge; these edges are MST edges and are contracted.
• Each phase at least halves the number of vertices, so there are $O(\log n)$ phases.
• Crucially, the class of planar graphs is closed under edge contraction (minor-closed), so every intermediate graph stays planar and keeps $O(\text{current vertex count})$ edges.

The work in phase $i$ is linear in the current size. With contraction the vertex count drops geometrically:

$\sum_{i\ge 0} c\,\frac{n}{2^{i}} = c\,n\sum_{i\ge 0}\frac{1}{2^{i}} = 2cn = \Theta(n).$

Using a linear-time planar contraction step (cleaning up parallel edges and self-loops in $O(\text{size})$ each round), the total cost telescopes to $\Theta(n)$. This is the classical Cheriton–Tarjan / Mareš result: the MST of a planar graph can be found in $\Theta(n)$ time — and $\Theta(n)$ is also a lower bound since every edge must in effect be examined, so the tight bound is $\Theta(n)$.

Hence the best (tightest) achievable bound is $\Theta(n)$, option 1.

Exam trick: "Planar" silently caps edges at $m=O(n)$ and is minor-closed, so Borůvka contraction stays linear-size each round and the geometric sum collapses to $\Theta(n)$ — beating the generic $\Theta(n\log n)$ that Prim/Kruskal would give.