給定一個城市地圖，標示出所有住家及道路。市政府希望當任一住家發生緊急狀況時，至少有一位消防義工可以僅經過一條道路就到 達該住家。為了人力精簡，需找出最少數量的義工配置方式。請問上述這個問題與下列哪個資訊科學概念最相關？
A最短路徑演算法(Shortest Path Algorithm)
B支配集合問題(Dominating Set)正確答案
C最小生成樹(Minimum Spanning Tree)
D圖著色問題(Graph Coloring Problem)
答案與詳解
為什麼答案是 B
支配集合（Dominating Set）的定義為圖中的一個頂點子集，使得圖中任一頂點要么在該子集中，要么與該子集中的頂點相鄰。求最少義工數量即為求解最小支配集合，完全符合題意。
載入中…
