第十一章：通訊網路 — 動畫敘事
第十一集 · Ch.11 通訊網路
封包的旅程
你發一封 LINE 訊息，它被切成幾十個封包，
每個封包走不同路徑，最後在對方手機重新組裝。
這背後是圖論在運作——
最短路徑、最大流量、容錯設計。
每個封包走不同路徑，最後在對方手機重新組裝。
這背後是圖論在運作——
最短路徑、最大流量、容錯設計。
網路模型
通訊網路的圖論模型
節點 = 路由器或主機
邊 = 通訊連線（有時有權重 = 延遲或頻寬）
封包路由 = 在圖上找路徑
關鍵問題：最短路徑、最大流量、容錯（去掉幾條邊後還能連通？）
邊 = 通訊連線（有時有權重 = 延遲或頻寬）
封包路由 = 在圖上找路徑
關鍵問題：最短路徑、最大流量、容錯（去掉幾條邊後還能連通？）
最短路徑 — Dijkstra 演算法互動
從節點 A 出發，點擊節點依序展開最短路徑：
點擊節點逐步展開最短路徑（從 A 出發）
最大流量 — Max-Flow Min-Cut
從源點到匯點，最多能傳多少資料？
等於「最小割」——切斷哪幾條邊能斷開連線，那些邊的容量之和就是最大流。
等於「最小割」——切斷哪幾條邊能斷開連線，那些邊的容量之和就是最大流。
最大流定理
最大流 = 最小割容量
（Ford-Fulkerson 定理）
網路能承載的最大流量，等於最脆弱的瓶頸截面。
（Ford-Fulkerson 定理）
網路能承載的最大流量，等於最脆弱的瓶頸截面。
應用場景
• 網路頻寬規劃
• 交通流量優化
• 供應鏈最大產能
• 影像分割（電腦視覺）
• 交通流量優化
• 供應鏈最大產能
• 影像分割（電腦視覺）
容錯設計 — 連通度
一個網路至少要切斷幾條邊，才能讓兩個節點失去連線？這叫做邊連通度。
k=1
連通度 1：只需切斷一條邊就能斷開——單點故障風險高
k=2
連通度 2：需切斷至少兩條邊才能斷開——容忍單點故障
k≥3
高連通度：軍事或關鍵基礎設施網路的設計目標——多重備援
觀念測驗
「最大流等於最小割」這個定理的含義是？
小結
1 / 7
本頁為動畫敘事版。看完後可前往 完整第十一章 進行互動練習。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)