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