20. 給定一個城市地圖，標示出所有住家及道路。市政府希望當任一住家發生緊急狀況時，至少有一位消防義工可以僅經過一條道路就到達該住家。為了人力精簡，需找出最少數量的義工配置方式。請問上述這個問題與下列哪個資訊科學概念最相關？
(A) 最短路徑演算法(Shortest Path Algorithm)
(B) 支配集合問題(Dominating Set)
(C) 最小生成樹(Minimum Spanning Tree)
(D) 圖著色問題(Graph Coloring Problem)

好的，我們來分析這個問題，並將其與資訊科學的概念進行配對。

問題描述：

• 有城市地圖，標示住家和道路。
• 任何住家發生緊急狀況時，至少有一位消防義工可以僅經過一條道路就到達該住家。
• 目標是找出最少數量的義工配置方式。

我們可以將這個問題建模為一個圖論問題：

• 節點 (Vertices)： 住家 (house)
• 邊 (Edges)： 道路 (road)
• 目標： 在圖中選擇最少數量的節點（義工的配置地點），使得圖中所有其他的節點（住家）都與所選的節點（義工所在地）相鄰（即僅經過一條道路）。

現在來看看各個資訊科學概念：

• (A) 最短路徑演算法 (Shortest Path Algorithm)

  • 目的是找到兩個節點之間的最短路徑（例如 Dijkstra 演算法、Floyd-Warshall 演算法）。
  • 題目要求的是覆蓋所有住家，而不是找到兩點之間的最短路徑。
  • 不相關。

• (B) 支配集合問題 (Dominating Set)

  • 支配集合問題的定義是：在一個圖 G=(V,E) 中，尋找一個最小的子集 D⊆V，使得對於任意不在 D 中的節點 v∈V∖D，都存在一個節點 u∈D 使得 u 與 v 相鄰（即有一條邊連接 u 和 v）。
  • 這與題目描述完全吻合。義工所在的節點就是支配集合中的節點，所有住家（包括義工所在的住家）都必須被「支配」（即在一條路的距離內）。題目要求「最少數量的義工」，這就是尋找最小支配集合 (Minimum Dominating Set)。
  • 高度相關。

• (C) 最小生成樹 (Minimum Spanning Tree)

  • 目的是在一個連通的加權圖中，找到一個邊的子集，使得這些邊連接了圖中所有的節點，且總權重最小，並且沒有形成環。
  • 題目沒有提到邊的權重，也沒有要求連接所有住家，而是要求覆蓋。
  • 不相關。

• (D) 圖著色問題 (Graph Coloring Problem)

  • 目的是用最少的顏色為圖中的每個節點著色，使得任意兩個相鄰的節點顏色不同。
  • 這與消防義工的配置問題沒有直接關係。
  • 不相關。

因此，這個問題與支配集合問題最相關。

The final answer is B​