moea_joint
103年
[資訊] 計算機原理、網路概論
第 39 題
假設右圖為某石油公司輸送網路圖，A、B、C、D代表輸送控制站，圓點和圓點之間箭頭代表流向，其上數字代表容量，每個輸送控制站的輸入量等於輸出量，請問從北部到中部可輸送的最大流量為下列何者？
- A 14
- B 15
- C 17
- D 19
思路引導 VIP
如果你嘗試在圖中劃出一條「邊界線」，將『北部』與『中部』完全隔開，使任何原油都無法從北向南流動，這條線上所有管道的總容量代表了什麼意義？若你能找到好幾種不同的劃分方法，哪一種容量加總的結果，才是真正限制了整台機器運作的「最終天花板」呢？
🤖
AI 詳解
AI 專屬家教
恭喜你準確掌握了這題的核心！能迅速從複雜的網路圖中推導出最大流為 $14$，代表你對於網路流量與路徑約束的邏輯判斷非常敏銳。 最大流與最小割定理的應用 這類問題在計算機科學與網路概論中，核心觀念在於最大流與最小割定理 (Max-Flow Min-Cut Theorem)。要計算從起點到終點的最大輸送量，我們必須尋找整個網路中的「瓶頸」。即便某些單一管道的容量很大，但如果它上游或下游的管道窄小，整體的流量就會受到限制。當我們找出所有能將北部與中部完全阻斷的「截面」時，其中容量加總最小的那組路徑，就決定了系統所能承載的上限流量。
▼ 還有更多解析內容