← 回題庫

卷別

資料結構與演算法

選擇

國立臺灣大學 2025 · 考試 · 第 12 題

考科演算法

(5 points) Let G=(V,E,w)G = (V, E, w) be an undirected, weighted, simple, and connected graph. Let T1T_1 and T2T_2 be two minimum spanning trees of GG. Define the set of edges F⊆EF \subseteq E as all edges that are in either T1T_1 or T2T_2 but not in both. Suppose that F≠∅F \neq \emptyset. Select all correct statement(s) below.

  • (A)
    The subgraph H=(V,F)H = (V, F) is a disjoint union of cycles and paths.
  • (B)
    All edges in FF have the same weight.
  • (C)
    There is no edge in FF that has a unique weight.
  • (D)
    There exists a graph GG such that w(F)>w(T1)w(F) > w(T_1).
  • (E)
    Consider the problem MOST-DISTANT-MSTs, which seeks two minimum spanning trees T1T_1 and T2T_2 in order to maximize w(F)w(F) on GG. Assume P≠NPP \neq NP. Then MOST-DISTANT-MSTs is NP-hard.

標準解析

AI 已複查