1. 從“七橋問題”到現代網絡為什么圖論是數學建模的“瑞士軍刀”如果你參加過數學建模競賽或者處理過任何涉及“關系”和“連接”的問題比如社交網絡分析、交通路線規劃、物流配送優化甚至是芯片電路設計那你大概率已經和“圖論”打過交道了。它不像微積分那樣直觀也不像線性代數那樣有整齊的矩陣但圖論提供了一種描述“事物之間關系”的絕佳語言。簡單來說圖論研究的對象就是由“點”和“線”構成的“圖”。點代表實體線代表實體之間的關系。這個看似簡單的模型卻能抽象出從互聯網結構到蛋白質相互作用的無數復雜系統。在數學建模中圖論常常扮演著“幕后軍師”的角色。當問題描述中出現“網絡”、“路徑”、“連通”、“最短”、“最大流”、“聚類”這些關鍵詞時圖論的工具箱就該登場了。無論是國賽、美賽還是亞太杯從經典的“公交線路查詢”2000年國賽B題到近年熱門的“物流配送”、“網絡輿情傳播”、“芯片布局優化”圖論模型都是解決這類問題的核心框架。它之所以強大是因為它將一個具體、雜亂的實際問題轉化成了一個可以用嚴謹數學方法算法來分析和求解的抽象模型。掌握了圖論就等于在數學建模的武器庫里添上了一把多功能的“瑞士軍刀”。2. 圖的基石如何用數學語言描述你的問題在動手建模之前我們必須先把現實世界“翻譯”成圖論的語言。這一步至關重要它決定了后續所有分析的起點是否正確。2.1 圖的定義與分類不只是點和線一個圖G通常定義為二元組(V, E)其中V是頂點的集合E是邊的集合。邊e ∈ E連接兩個頂點u, v ∈ V可以記作(u, v)或e uv。根據邊的性質圖可以分為幾大類選擇哪種類型直接對應著問題的不同假設無向圖 vs. 有向圖這是最基礎的分類。無向圖邊沒有方向。例如在描述城市間的公路網假設所有公路都是雙向的、社交網絡中的好友關系A是B的好友則B也是A的好友時我們使用無向圖。邊(u, v)和(v, u)是同一條邊。有向圖邊有方向用箭頭表示。例如在描述網頁之間的超鏈接A網頁鏈接到B網頁但B不一定鏈接回A、交通流中的單行道、任務之間的依賴關系任務A完成后才能開始任務B時必須使用有向圖。此時(u, v)和(v, u)是兩條不同的邊。無權圖 vs. 帶權圖無權圖我們只關心頂點之間“是否相連”。邊沒有附加的數值信息。帶權圖每條邊有時甚至是每個頂點都被賦予一個權值。這個權值可以代表距離、時間、成本、流量容量、相關性強度等等。例如在尋找最短路徑時地圖就是一個帶權圖權值是道路長度或通行時間。簡單圖 vs. 多重圖簡單圖任意兩個頂點之間最多只有一條邊且沒有頂點連接到自身的邊自環。大多數理論分析和經典算法都基于簡單圖。多重圖允許兩個頂點之間存在多條平行的邊。這在建模某些交通網絡兩地間有多條不同班次的航線或電路網絡時有用。建模心得很多新手在第一步就會出錯。比如在建模“微博信息傳播”時如果A轉發B的微博信息是從B流向A這是一個有向的關系。如果你錯誤地建成了無向圖就意味著信息可以雙向等概率傳播這顯然與事實不符會導致后續的傳播模型完全失效。所以花時間厘清關系的方向性和是否需要權重是建模成功的基石。2.2 圖的存儲計算機如何“認識”一張圖當我們用編程實現圖論算法時無論是用 MATLAB、Python 還是其他工具首先需要解決的是圖的存儲問題。主要有兩種主流方法各有優劣鄰接矩陣用一個n x n的矩陣A來表示一個具有n個頂點的圖。如果頂點i和j之間有邊則A[i][j] 1無權圖或A[i][j] w權值。對于無向圖矩陣是對稱的。優點直觀檢查任意兩個頂點是否相鄰非常快O(1)時間復雜度。缺點占用空間大O(n2)對于頂點很多但邊很稀疏的圖如社交網絡空間浪費嚴重。鄰接表為每個頂點維護一個列表記錄所有與它相鄰的頂點及邊的權值。優點空間效率高只存儲存在的邊空間復雜度為 O(|V||E|)。遍歷某個頂點的所有鄰居非常高效。缺點檢查任意兩個頂點是否相鄰需要遍歷其中一個頂點的鄰接表速度較慢最壞 O(n)。選擇建議在數學建模中如果圖規模不大比如頂點數1000用鄰接矩陣更容易編程和調試。如果圖規模巨大且稀疏如數萬個網頁的鏈接關系鄰接表是唯一的選擇。Python 的networkx庫、MATLAB 的graph和digraph對象都內部采用了高效的存儲方式我們可以直接調用但理解其背后的原理有助于我們寫出更高效的代碼。3. 圖論核心算法工具箱從尋路到規劃將問題抽象成圖之后接下來就是調用各種算法來“解圖”。下面這幾個算法是數學建模中最常被用到的“明星算法”。3.1 最短路徑問題找到最優連接這是圖論最經典的應用之一。給定一個帶權圖權值代表距離、成本或時間和起點、終點找到一條路徑使得沿途的權值之和最小。Dijkstra算法解決非負權圖的單源最短路徑問題從一個起點到圖中所有其他頂點的最短路徑。核心思想一種貪心策略。維護一個“已確定最短距離”的頂點集合 S。每次從尚未確定的頂點中選擇一個距離起點最近的頂點加入 S并利用這個新確定的頂點去更新它所有鄰居的距離估計。為什么權值不能為負Dijkstra 算法的貪心假設是一旦一個頂點被加入 S其最短距離就確定了。如果存在負權邊后來可能通過一條包含負權邊的路徑讓這個距離變得更短從而破壞算法的正確性。建模應用城市導航道路長度非負、網絡數據包路由延遲非負、項目關鍵路徑分析任務時間非負。在 2024 年數學建模國賽 C 題關于物流配送的問題中配送中心到各個客戶點的最短行車路徑就可以用 Dijkstra 算法求解。Floyd-Warshall算法解決任意兩點之間的最短路徑問題。核心思想動態規劃。定義dist[i][j][k]為從頂點 i 到 j且中間只經過編號不超過 k 的頂點的最短路徑長度。通過三重循環逐步“允許”更多的頂點作為中轉站。優缺點代碼極其簡潔三重 for 循環能一次性求出所有點對之間的最短距離。但時間復雜度是 O(n3)因此只適用于頂點規模不大n 500的稠密圖。建模應用需要預先計算所有地點之間距離的全局規劃問題。例如在多個配送中心協同調度時可能需要頻繁查詢任意兩個客戶點之間的最短距離用 Floyd 算法預處理出一個距離矩陣會非常方便。A搜索算法*在 Dijkstra 基礎上加入了啟發式函數用于在已知終點時加速搜索。核心思想不僅考慮從起點到當前頂點的實際代價g(n)還估計從當前頂點到終點的預計代價h(n)。每次優先擴展f(n) g(n) h(n)最小的頂點。h(n)是一個啟發函數例如在網格地圖中常用曼哈頓距離或歐幾里得距離。關鍵啟發函數h(n)必須滿足可采納性不能高估實際代價才能保證找到最優解。如果h(n) 0A* 就退化為 Dijkstra。建模應用游戲 AI 尋路、機器人路徑規劃、帶有地理信息約束的路徑搜索。當圖非常大且我們對終點位置有先驗知識時A* 比 Dijkstra 快得多。實操避坑使用 Dijkstra 算法時務必檢查圖中是否有負權邊。一個常見的坑是當用“利潤”或“收益”作為權值并想求“最大收益路徑”時有人會簡單地將權值取負然后套用 Dijkstra 求最短路徑。這只有在所有收益都為負即原權值為正時才等價。如果原權值有正有負取負后會出現負權環Dijkstra 算法失效。此時應使用可以處理負權邊的 Bellman-Ford 算法或將其轉化為網絡流問題。3.2 最小生成樹用最經濟的成本連接所有節點想象你要為幾個村莊鋪設電網或光纖要求所有村莊都能連通且總線路長度最短。這就是最小生成樹的典型場景。Prim算法從一個頂點開始逐步“生長”出一棵樹。核心思想維護兩個集合已在樹中的頂點集合 T和尚未在樹中的頂點集合。每次從連接 T 與外部頂點的所有邊中選擇一條權值最小的邊并將該邊及其連接的外部頂點加入 T。實現通常使用優先隊列最小堆來高效地選取最小邊時間復雜度為 O(|E| log|V|)。Kruskal算法按邊權從小到大嘗試加入并避免形成環。核心思想將所有邊按權值從小到大排序。依次考慮每條邊如果這條邊連接的兩個頂點目前不在同一個連通分量中加入它不會形成環就選中這條邊并將兩個連通分量合并。直到選中了 n-1 條邊為止。實現排序需要 O(|E| log|E|)而判斷和合并連通分量需要使用并查集數據結構其單次操作平均時間復雜度接近常數。因此總復雜度主要由排序決定。算法選擇對比特性Prim算法Kruskal算法適用圖稠密圖稀疏圖時間復雜度O(V思想像“生長”一棵樹像“拼接”一棵樹實現關鍵優先隊列并查集建模應用除了網絡建設最小生成樹還用于聚類分析通過斷開樹中權值最大的邊來進行層次聚類、圖像分割、以及一些近似算法中。在 2022 年數學建模國賽 C 題古代玻璃制品的成分分析中雖然主體是統計分析但若想分析不同類別文物化學成分的“關聯網絡”最小生成樹可以幫助提煉出最核心的關聯關系。3.3 網絡流與最大流/最小割建模資源傳輸的極限當圖中的邊代表管道權值代表管道容量我們需要計算從源頭源點到目的地匯點能傳輸的最大流量時就需要網絡流模型。最大流問題給定一個有向的流量網絡邊有容量求從源點 s 到匯點 t 的最大流量。Ford-Fulkerson 方法核心框架是不斷尋找增廣路徑從 s 到 t 的、剩余容量為正的路徑并沿該路徑推送盡可能多的流量直到找不到增廣路徑為止。Edmonds-Karp 算法是 Ford-Fulkerson 方法的一個具體實現規定每次用 BFS 尋找最短的增廣路徑。這保證了算法一定能在 O(|V| * |E|2) 時間內終止避免了某些情況下無限循環或效率極低的問題。Dinic 算法更高效的算法通過引入“分層圖”和“阻塞流”的概念時間復雜度優化到 O(|V|2 * |E|)在實際競賽和工程中更為常用。最小割問題與最大流問題緊密相關。一個割是將頂點集 V 分成包含源點 s 的集合 S 和包含匯點 t 的集合 T。割的容量是所有從 S 指向 T 的邊的容量之和。最大流最小割定理指出網絡中從 s 到 t 的最大流量等于分隔 s 和 t 的最小割的容量。這個定理極其強大它意味著求最大流和求最小割是等價問題。算法在求出最大流的同時實際上也找到了一個最小割。建模應用交通規劃道路網絡的最大通行能力。數據傳輸通信網絡的最大帶寬。資源分配匹配問題如求職者與崗位。可以轉化為一個最大流問題建立源點連接所有求職者、中間層求職者與崗位的匹配關系容量為1、匯點連接所有崗位。最大流量就是最大匹配數。圖像分割將圖像像素劃分為前景和背景。可以構建一個流網絡其中像素作為頂點與源點前景和匯點背景的邊權代表屬于前景/背景的概率像素之間的邊權代表相似性。最小割就對應著能量最小的分割方案。個人體會網絡流問題的難點往往不在于算法實現有很多現成庫而在于如何將實際問題巧妙地轉化為網絡流模型。識別出問題中的“源”、“匯”、“容量”和“流量守恒”中間節點流入等于流出是建模的關鍵。一旦轉化成功問題就變成了一個標準的、有成熟解法的問題。4. 圖的深入性質與應用洞察復雜系統的結構除了解決具體的優化問題圖論還提供了一系列工具來刻畫圖的整體結構特性這對于分析復雜系統至關重要。4.1 連通性與中心性誰是這個網絡的關鍵連通分量無向圖連通分量極大連通子圖。可以用深度優先搜索DFS或廣度優先搜索BFS輕松找出所有連通分量。這對于檢查網絡的整體連通性例如社交網絡中是否存在孤立的群體非常有用。有向圖強連通分量在有向圖中如果一個子圖內任意兩個頂點都可以互相到達則該子圖是一個強連通分量。求解強連通分量的經典算法是Kosaraju 算法或Tarjan 算法。這可以用于分析網頁鏈接形成的社區一組互相緊密鏈接的網頁或者循環依賴的模塊。中心性度量用于量化圖中頂點的重要性。度中心性一個頂點的鄰居數。最簡單直觀在社交網絡中度中心性高的人就是“交友廣泛”的人。接近中心性一個頂點到圖中所有其他頂點的最短路徑距離之和的倒數。值越大說明該頂點在信息傳播中越處于中心位置到其他頂點“越快”。中介中心性一個頂點出現在任意兩個頂點最短路徑上的次數。中介中心性高的人或節點是網絡中的“橋梁”或“樞紐”控制著信息或資源的流動。例如在航空網絡中某個機場的中介中心性高意味著它是許多航線不可或缺的中轉站。特征向量中心性認為一個頂點的重要性取決于其鄰居的重要性。這類似于網頁排名的 PageRank 算法的思想。一個頂點即使鄰居不多但如果它的鄰居都是重要頂點那么它自己也重要。建模應用在“輿情傳播”、“關鍵節點識別”類題目中如某些賽題中尋找影響輿論的關鍵人物中心性分析是核心步驟。你需要根據問題背景選擇合適的中心性指標。例如如果想找出傳播謠言最快的人應關注接近中心性如果想找出一旦被控制就能最大程度破壞網絡連通性的人應關注中介中心性。4.2 圖的匹配與著色解決分配與沖突問題匹配問題在圖 G 中一個匹配是一個邊的集合其中任意兩條邊都沒有公共頂點。最大匹配是包含邊數最多的匹配。二分圖匹配如果圖的頂點可以被分成兩個不相交的集合如求職者和崗位且所有邊都連接著分屬不同集合的頂點則該圖是二分圖。二分圖的最大匹配可以用匈牙利算法高效求解。建模應用任務分配、學員選課、廣告投放廣告與廣告位匹配。在 2025 年研究生數學建模 D 題或類似調度問題中將任務和資源建模為二分圖的兩部分用匈牙利算法求最大匹配是一種經典的思路。圖著色問題給圖的每個頂點分配一種顏色使得任何一條邊連接的兩個頂點顏色不同。所需的最少顏色數稱為圖的色數。應用本質上是一個資源分配沖突避免問題。經典例子是課程表安排頂點是課程如果兩門課有共同的學生就在它們之間連一條邊。給頂點著色就是給課程安排時間每種顏色代表一個時間段要求有沖突的課程不同色。色數就是所需的最少時間段數。求解圖著色是 NP 難問題對于一般圖沒有快速精確算法。實踐中常使用貪心算法如 Welsh-Powell 算法求近似解或者使用回溯法、整數規劃求小規模圖的精確解。實操技巧對于匹配問題首先要判斷你的圖是否是二分圖。一個簡單的判定方法是使用 BFS 或 DFS 進行二著色從任意頂點開始將其染成紅色將其所有鄰居染成藍色再將鄰居的鄰居染成紅色……如果在染色過程中發現某個鄰居的顏色與當前頂點相同則不是二分圖。如果圖不是二分圖問題就變成了更復雜的“一般圖匹配”需要使用開花樹算法等難度大增。在建模時應盡量通過合理的抽象將問題轉化為二分圖匹配。5. 從模型到代碼數學建模中的圖論實戰理論再漂亮最終也要落地為代碼和論文。這部分分享一些將圖論應用于數學建模競賽的實戰經驗。5.1 工具鏈選擇MATLAB vs. Python這是數學建模中最常見的兩個選擇。MATLAB優點內置了強大的圖論工具箱。graph和digraph對象創建非常方便shortestpath(Dijkstra)、minspantree(Prim)、maxflow、centrality等函數一鍵調用對于快速原型驗證和求解標準問題極其友好。繪圖功能強大能輕松生成美觀的網絡圖。缺點處理超大規模圖時性能可能不如 Python 的一些庫靈活。自定義復雜算法時語法不如 Python 簡潔。適用場景國賽、美賽中問題規模適中追求快速出結果和漂亮可視化時MATLAB 是首選。Python優點生態豐富。networkx庫提供了極其全面的圖論算法實現和網絡分析功能。scipy.sparse可以高效處理稀疏矩陣鄰接矩陣。與numpy,pandas,matplotlib等庫無縫集成進行數據預處理和后分析非常方便。對于需要自定義復雜算法或集成機器學習模型的情況Python 更靈活。缺點networkx純 Python 實現對于超大規模圖百萬頂點以上的計算性能是瓶頸但通常數學建模競賽的規模達不到這個級別。適用場景亞太杯等競賽或者問題涉及復雜的數據預處理、需要與其他 AI/統計模型結合時Python 是更強大的選擇。我的建議隊伍里至少有一人熟練掌握其中一種工具鏈。對于新手隊伍如果時間緊迫MATLAB 的上手速度更快。對于想追求更高靈活性和處理復雜問題的隊伍Python 是更長遠的選擇。很多優秀的論文往往是混合使用比如用 Python 做數據清洗和復雜建模用 MATLAB 做某個特定算法的求解和繪圖。5.2 建模流程與論文書寫要點一個完整的圖論建模流程通常包括問題抽象與圖定義明確頂點是什么邊是什么邊是否有向、是否有權。這是最重要的一步要在論文中清晰闡述。模型選擇與建立根據問題目標最短路徑、最大流、最小連接、關鍵節點識別等選擇對應的圖論模型。論證為什么這個模型適合本問題。算法選擇與求解說明選用什么算法Dijkstra, Floyd, Prim, Edmonds-Karp, 匈牙利算法等并簡述算法步驟。如果算法有變種或參數如 A* 的啟發函數需要說明設計理由。結果分析與可視化給出算法輸出的結果如最短路徑長度、最大流量值、最小生成樹結構、關鍵節點列表等。務必進行可視化繪制出網絡圖用節點大小、顏色、邊的粗細來直觀展示權重、流量、中心性等結果。一張好的圖勝過千言萬語。模型檢驗與推廣討論模型的靈敏度比如某條邊的權值變化對結果的影響、魯棒性隨機移除一些節點或邊網絡性能如何變化。思考模型還可以應用到哪些類似場景。論文避坑指南忌“黑箱”操作不要只寫“我們使用了 networkx 庫的 shortest_path 函數”而要寫出你構建的圖是什么調用的是什么算法如 Dijkstra甚至可以寫出算法的偽代碼或核心步驟。忌只有文字沒有圖圖論模型天然適合可視化。在論文中放入清晰美觀的網絡結構圖、最短路徑示意圖、流量分布圖、中心性排名柱狀圖等能極大提升論文的可讀性和說服力。忌模型單薄很多問題不能僅用一個圖論模型解決。例如物流配送問題可能先要用圖論求最短路徑再用線性規劃或啟發式算法進行車輛路徑規劃。圖論常常是復雜模型中的一個關鍵模塊。要在論文中清晰闡述各個模塊是如何銜接的。重視復雜度分析在“模型評價”部分分析你所采用算法的時間復雜度和空間復雜度說明其對問題規模的承受能力。這體現了你對模型深度的理解。5.3 一個綜合案例社區快遞點選址問題假設一個賽題要求為某個大學校園規劃新的快遞收發點目標是讓學生從宿舍到快遞點的平均距離最短且建設成本與點數有關不能太高。抽象將校園道路交叉口、宿舍樓入口、備選快遞點位置抽象為頂點。將校園道路抽象為邊權值為道路的實際長度或步行時間。宿舍樓頂點有“需求權重”學生人數。建模這是一個設施選址問題的變種。可以建立這樣一個模型假設只能選 k 個點建快遞點。對于每個宿舍樓其“不便利度”定義為該宿舍樓到最近快遞點的最短距離乘以該樓的學生人數。目標最小化所有宿舍樓的“不便利度”之和。求解這是一個 NP-Hard 的組合優化問題。常用啟發式算法求解如貪心算法每次選擇一個能最大程度降低總不便利度的位置直到選滿 k 個。模擬退火/遺傳算法將 k 個點的選擇作為一個解進行全局優化。在每一步中都需要調用Dijkstra 算法多次來計算每個宿舍樓到當前選址方案中最近點的距離。分析可以繪制出最終選址的網絡圖用不同顏色標記快遞點和宿舍樓用線的粗細表示服務關系。分析當 k 變化時總不便利度的下降曲線為決策提供“性價比”參考。通過這個例子可以看到圖論最短路徑算法是整個求解過程中的一個核心計算子模塊它與優化算法緊密結合共同解決了實際問題。圖論的精妙之處在于它用極其簡潔的數學結構捕捉了萬物之間聯系的骨架。在數學建模中它更像是一種思維模式當你看到“關系”、“網絡”、“路徑”、“分配”這些字眼時能立刻聯想到點與線并能從豐富的算法工具箱里挑選出合適的工具。這種能力需要通過學習和實踐一個個具體的模型和算法來積累。從看懂一篇優秀論文中的圖模型開始到自己動手用代碼實現一個最短路徑算法再到完整地解決一個綜合性的賽題每一步都在加深你對這種強大建模語言的理解。