2025年大學(xué)《數(shù)理基礎(chǔ)科學(xué)》專業(yè)題庫——網(wǎng)絡(luò)流問題及算法考試時(shí)間：______分鐘總分：______分姓名：______一、簡述網(wǎng)絡(luò)流模型中，可行流、最大流、割的概念及其相互關(guān)系。二、Ford-Fulkerson算法的核心思想是什么？請(qǐng)簡述其基本步驟。在什么條件下，F(xiàn)ord-Fulkerson算法能保證找到最大流？三、Dinic算法與Edmonds-Karp算法相比，其主要優(yōu)缺點(diǎn)是什么？Dinic算法中處理阻塞流的關(guān)鍵步驟是什么？四、寫出網(wǎng)絡(luò)單純形法求解最小費(fèi)用流問題的基本步驟。在應(yīng)用網(wǎng)絡(luò)單純形法時(shí)，如何選擇入基變量和出基變量？五、已知一個(gè)網(wǎng)絡(luò)流問題，其流量值為f*。現(xiàn)要找到一個(gè)割(S,T)，使得該割的容量等于f*。請(qǐng)簡述如何根據(jù)最大流-最小割定理來構(gòu)造這個(gè)割，并解釋其容量為何等于流量值f*。六、請(qǐng)證明增廣路徑定理：一個(gè)網(wǎng)絡(luò)流是最大流當(dāng)且僅當(dāng)不存在關(guān)于該流的增廣路徑。七、考慮一個(gè)最小費(fèi)用流問題：網(wǎng)絡(luò)中每條弧除了容量c(u,v)外，還有單位費(fèi)用e(u,v)。要求在滿足流量需求的前提下，使得總費(fèi)用最小。請(qǐng)描述如何將此問題轉(zhuǎn)化為標(biāo)準(zhǔn)的最小費(fèi)用流問題（即所有供應(yīng)點(diǎn)或需求點(diǎn)匯入超級(jí)源點(diǎn)或超級(jí)匯點(diǎn)）。八、假設(shè)你正在設(shè)計(jì)一個(gè)算法來解決如下問題：給定一個(gè)網(wǎng)絡(luò)G=(V,E)，和一個(gè)正整數(shù)k。判斷是否存在一個(gè)流f，其流量值為k，且滿足所有容量約束。請(qǐng)描述你的算法思路，并分析其大致的時(shí)間復(fù)雜度（可以基于已學(xué)過的算法）。九、在一個(gè)容量為C的網(wǎng)絡(luò)上，如果存在一個(gè)流量值為f的最大流，且f=C。證明：網(wǎng)絡(luò)中必存在一條從源點(diǎn)s到匯點(diǎn)t的路徑，該路徑上所有弧的容量均未被飽和（即剩余容量均大于0）。十、描述如何將一個(gè)任務(wù)分配問題（例如，n個(gè)任務(wù)分配給m個(gè)工人，每個(gè)工人完成某任務(wù)的時(shí)間已知，目標(biāo)是使得所有任務(wù)完成的總時(shí)間最短）轉(zhuǎn)化為最小費(fèi)用流問題。請(qǐng)說明網(wǎng)絡(luò)中各參數(shù)（容量、費(fèi)用、流量）的設(shè)置方法。試卷答案一、*概念：*可行流：指網(wǎng)絡(luò)G=(V,E)中一個(gè)定義在弧集E上的函數(shù)f=(f(u,v))，滿足：①對(duì)任意弧(u,v)∈E，有0≤f(u,v)≤c(u,v)（容量約束）；②對(duì)除源點(diǎn)s和匯點(diǎn)t以外的任意頂點(diǎn)u∈V，有∑_{v:(u,v)∈E}f(u,v)=∑_{v:(v,u)∈E}f(v,u)（流量守恒）。*最大流：指網(wǎng)絡(luò)G=(V,E)中一個(gè)可行流f，其流量值f*=∑_{v:(s,v)∈E}f(s,v)-∑_{v:(v,s)∈E}f(v,s)（通常定義為從源點(diǎn)s出發(fā)，流向其余頂點(diǎn)的總流量）是所有可行流中最大的。*割(S,T)：指將頂點(diǎn)集V劃分為兩個(gè)不相交的子集S和T，使得源點(diǎn)s∈S，匯點(diǎn)t∈T，且S∪T=V，S∩T=?。割(S,T)對(duì)應(yīng)的弧集為{(u,v)∈E|u∈S,v∈T}，該割的容量記為c(S,T)=∑_{(u,v)∈(S,T)}c(u,v)。*關(guān)系：最大流-最小割定理指出，網(wǎng)絡(luò)G中最大流的流量值f*等于任何割(S,T)的容量c(S,T)。該定理表明，最大流值受到“割”的限制，即要從源點(diǎn)將流量送出，必須跨越某些弧，這些弧構(gòu)成一個(gè)割，其容量提供了送出最大流量的理論上限。因此，最大流值等于能分割網(wǎng)絡(luò)（將s與t隔開）的最小“障礙”的容量。二、*核心思想：Ford-Fulkerson算法的核心思想是：只要在殘留網(wǎng)絡(luò)中存在從源點(diǎn)s到匯點(diǎn)t的增廣路徑，就將該路徑上的流量沿著殘留網(wǎng)絡(luò)的方向增加（即沿前向弧增加流量，沿反向弧減少流量），從而增加當(dāng)前流的流量值，直到殘留網(wǎng)絡(luò)中不再存在增廣路徑為止。*基本步驟：1.初始化：令初始可行流f為0（即所有弧的流量為0）。2.尋找增廣路徑：在當(dāng)前的殘留網(wǎng)絡(luò)N_f中，使用BFS或DFS尋找一條從s到t的增廣路徑P（P是N_f中從s到t的有向路徑）。3.計(jì)算增廣量：在路徑P上，找到所有前向弧的最小剩余容量，記為δ=min{c_f(u,v)|(u,v)∈P}。這個(gè)δ就是本次可以增加的流量。4.沿路徑調(diào)整流量：沿增廣路徑P的前向弧，將流量增加δ；沿增廣路徑P的反向弧，將流量減少δ。這樣調(diào)整后，路徑P上的所有弧的流量都更新了。5.更新殘留網(wǎng)絡(luò)：根據(jù)新的流量f，重新計(jì)算所有弧的剩余容量，得到新的殘留網(wǎng)絡(luò)N_f。6.重復(fù)：若N_f中存在增廣路徑，則返回步驟2；否則，算法結(jié)束，當(dāng)前流f即為最大流。*終止條件與保證：Ford-Fulkerson算法保證在殘留網(wǎng)絡(luò)中不存在增廣路徑時(shí)終止。此時(shí)，根據(jù)流量守恒和容量約束，該流即為最大流。其正確性基于增廣路徑定理：一個(gè)流是最大流當(dāng)且僅當(dāng)不存在關(guān)于該流的增廣路徑。三、*優(yōu)缺點(diǎn)：*優(yōu)點(diǎn)：*Dinic算法在稠密圖中通常比Ford-Fulkerson和Edmonds-Karp算法效率更高。*其時(shí)間復(fù)雜度為O(V^2E)，在實(shí)際應(yīng)用中表現(xiàn)良好。*算法實(shí)現(xiàn)相對(duì)清晰。*缺點(diǎn)：*Dinic算法比Ford-Fulkerson和Edmonds-Karp算法的實(shí)現(xiàn)更復(fù)雜一些。*在非常稀疏的圖中，其性能可能不如某些其他算法（如最高標(biāo)號(hào)法）。*阻塞流處理關(guān)鍵步驟：Dinic算法的核心在于高效地處理殘留網(wǎng)絡(luò)中的“阻塞流”（BlockingFlow）。關(guān)鍵步驟是：1.構(gòu)建分層圖：使用BFS從源點(diǎn)s出發(fā)，在殘留網(wǎng)絡(luò)N_f中構(gòu)建分層圖H_f，其中頂點(diǎn)分為層0（包含s）和層k（包含t），層i中的頂點(diǎn)v到層i+1中的頂點(diǎn)v'之間存在正向?。ㄈ萘看笥?）。如果殘留網(wǎng)絡(luò)中存在從s到t的路徑，則分層圖是連通的。2.預(yù)流推進(jìn)（PreflowPush）：在分層圖H_f中，利用拓?fù)湫颍◤膶?到層k）嘗試將流量從高層向低層推進(jìn)。對(duì)于層i中的頂點(diǎn)v，若其進(jìn)入弧的流量和大于其出去弧的流量和（即存在“溢出”），則將多余的流量沿任意一條指向低層（i+1）的正向弧推進(jìn)。這會(huì)可能導(dǎo)致某些弧的流量超過其容量，形成“過載”（Overflow）弧，過載弧的流量在后續(xù)步驟中需要被“推回”（PushBack）。3.尋找并處理阻塞流：當(dāng)分層圖不再連通（即s與t之間無路徑）時(shí)，當(dāng)前殘留網(wǎng)絡(luò)中的流構(gòu)成一個(gè)“阻塞流”。Dinic算法通過在分層圖中執(zhí)行“增廣路徑”操作來處理阻塞流：從層0開始，遞歸地尋找從s到t的路徑，并在路徑上增加流量，同時(shí)更新分層圖（可能需要重新分層）。這個(gè)過程會(huì)持續(xù)進(jìn)行，直到找到一條完整的增廣路徑，或者確認(rèn)當(dāng)前流已為最大流。通過不斷構(gòu)建分層圖和處理阻塞流，Dinic算法能夠高效地找到增廣路徑并增加流量。四、*基本步驟：1.初始化：令初始可行流f為0。選擇一個(gè)非飽和弧（即殘差網(wǎng)絡(luò)中容量大于0的?。┳鳛楫?dāng)前弧，通常選擇出度不為0且費(fèi)用最小的弧。如果沒有這樣的弧，則已達(dá)到最優(yōu)解。2.進(jìn)入基：將選定的非飽和弧加入當(dāng)前基（單純形表）。3.調(diào)整流：沿當(dāng)前基中的路徑（通常從源點(diǎn)開始，通過非飽和弧連接到匯點(diǎn)），找到路徑上的最小殘差容量δ。沿路徑前向弧增加流量δ，沿路徑反向弧減少流量δ。更新所有相關(guān)弧的流量和殘差。4.檢查最優(yōu)性：檢查是否所有需求點(diǎn)（如果是需求網(wǎng)絡(luò)）的流量需求都已滿足，且匯點(diǎn)的凈流出量等于總流量。如果是，則算法結(jié)束，當(dāng)前流即為最小費(fèi)用流。否則，進(jìn)入下一步。5.尋找離開基的?。涸诋?dāng)前基中，找到一條離開基的?。ㄍǔＪ琴M(fèi)用最高的弧，或者通過BFS/DFS找到匯點(diǎn)t的路徑上的?。?。6.更新基：沿離開基的弧和路徑，將基更新為新的基（移除離開的弧，加入新的增廣?。?。7.重復(fù)：返回步驟2，繼續(xù)迭代。*選擇入基和出基變量：*入基變量：通常選擇當(dāng)前殘留網(wǎng)絡(luò)中出度不為0且單位費(fèi)用（或?qū)ε甲兞颗c容量之差）最小的弧。這類似于單純形法中選擇“最低成本離開基”的規(guī)則，目的是盡量以最小的代價(jià)增加流量。*出基變量：當(dāng)沿著某個(gè)增廣路徑增加流量時(shí)，需要選擇一個(gè)弧離開基。這通常通過在當(dāng)前基形成的路徑上，找到“瓶頸”（路徑上的最小殘差容量δ）對(duì)應(yīng)的弧，或者在某些實(shí)現(xiàn)中，選擇匯點(diǎn)t所在的路徑上的弧作為離開基的弧。五、*構(gòu)造割：根據(jù)最大流-最小割定理，最大流的流量值f*等于某個(gè)割(S,T)的容量c(S,T)。當(dāng)算法終止時(shí)，殘留網(wǎng)絡(luò)中不再存在從s到t的路徑。這意味著，從源點(diǎn)s出發(fā)，所有能夠到達(dá)的頂點(diǎn)構(gòu)成集合S；所有不能到達(dá)的頂點(diǎn)（包括匯點(diǎn)t）構(gòu)成集合T。這樣的割(S,T)就是所謂的“分離割”。該割正好分離了源點(diǎn)s和匯點(diǎn)t。*容量證明：該割(S,T)的容量c(S,T)=∑_{(u,v)∈(S,T)}c(u,v)，即割上所有從S指向T的弧的原始容量之和。根據(jù)流量守恒：*從源點(diǎn)s出發(fā)，總共有f*的流量需要流出。這些流量必須通過割(S,T)上的弧才能從S流向T。*因此，割(S,T)上的總?cè)萘勘仨氈辽贋閒*，否則無法輸送足夠的流量。*同時(shí)，根據(jù)割的定義，任何從T到S的弧都不在割弧集中，其容量為0或未被使用。所以割的容量就是輸送f*流量所必須跨越的“最小障礙”的總?cè)萘?，即c(S,T)≥f*。*結(jié)合算法終止條件（無增廣路徑），此時(shí)的流f即為最大流，所以f*=c(S,T)。六、*證明：*（?）設(shè)f是最大流，證明不存在增廣路徑：假設(shè)存在一條關(guān)于流f的增廣路徑P。根據(jù)Ford-Fulkerson算法思想，我們可以沿著P增加一個(gè)正的流量δ（δ<c_f(u,v)對(duì)于所有前向弧(u,v)∈P，δ≤c_f(v,u)對(duì)于所有反向弧(v,u)∈P）。這樣得到的新流f'=f+δδ仍然是可行流（滿足容量約束和流量守恒），并且其流量值為f*+δ>f*。這與f*是最大流的假設(shè)矛盾。因此，不存在關(guān)于最大流f的增廣路徑。*（?）設(shè)不存在增廣路徑，證明f是最大流：假設(shè)流f不是最大流，那么存在另一個(gè)可行流f'，其流量值f*'>f*。根據(jù)Ford-Fulkerson算法的增廣路徑定理，從流f到流f'之間存在一條增廣路徑P。沿著P可以將流量從f增加到f'。這與“不存在增廣路徑”的假設(shè)矛盾。因此，不存在流量值大于f*的可行流，f*即為最大流。七、*思路：最小費(fèi)用流問題的目標(biāo)是使總費(fèi)用最小，而標(biāo)準(zhǔn)的最小費(fèi)用流問題通常假設(shè)所有流量最終匯集到匯點(diǎn)t，或者所有流量都由源點(diǎn)s提供。因此，需要將具有供應(yīng)和需求的點(diǎn)（生成點(diǎn)和匯入點(diǎn)）統(tǒng)一到源點(diǎn)和匯點(diǎn)。1.引入超級(jí)源點(diǎn)S和超級(jí)匯點(diǎn)T：*創(chuàng)建一個(gè)超級(jí)源點(diǎn)S。將所有原始供應(yīng)點(diǎn)u（供應(yīng)量為b(u)>0）連接到S。在弧(S,u)上設(shè)置容量c(S,u)=b(u)，單位費(fèi)用e(S,u)=0（因?yàn)楣?yīng)點(diǎn)不再產(chǎn)生費(fèi)用）。*創(chuàng)建一個(gè)超級(jí)匯點(diǎn)T。將所有原始需求點(diǎn)v（需求量為d(v)>0）連接到T。在弧(v,T)上設(shè)置容量c(v,T)=d(v)，單位費(fèi)用e(v,T)=0（因?yàn)閰R入點(diǎn)不再產(chǎn)生費(fèi)用）。2.處理原始?。?保持所有原始弧(u,v)∈E。其容量保持為c(u,v)，單位費(fèi)用保持為e(u,v)。3.處理原始供應(yīng)和需求：*超級(jí)源點(diǎn)S的總供應(yīng)量等于所有原始供應(yīng)點(diǎn)的供應(yīng)量之和，即b(S)=∑_{u:b(u)>0}b(u)。*超級(jí)匯點(diǎn)T的總需求量等于所有原始需求點(diǎn)的需求量之和，即d(T)=∑_{v:d(v)>0}d(v)。*流量守恒約束：為了保證原始供應(yīng)點(diǎn)u的流量確實(shí)等于其供應(yīng)量b(u)，可以在弧(S,u)和弧(u,T)之間添加一條虛弧(u,S)，容量為0，費(fèi)用為任意大正數(shù)（例如無窮大）。這樣，流量的分配將自動(dòng)滿足b(u)=流出u的流量-流入u的流量=c(S,u)-c(u,T)=b(u)-0。同樣地，為了確保原始需求點(diǎn)v的需求量d(v)得到滿足，可以在弧(v,T)和弧(T,v)之間添加一條虛弧(T,v)，容量為0，費(fèi)用為任意大正數(shù)。這樣，d(v)=流入v的流量-流出v的流量=c(v,T)-c(T,v)=d(v)-0。*另一種處理方式：可以將原始供應(yīng)點(diǎn)u看作是匯點(diǎn)，其“需求量”為-b(u)；將原始需求點(diǎn)v看作是源點(diǎn)，其“供應(yīng)量”為-d(v)。然后直接應(yīng)用標(biāo)準(zhǔn)最小費(fèi)用流模型。引入超級(jí)源點(diǎn)S和超級(jí)匯點(diǎn)T后，S的總供應(yīng)量為∑_{v:d(v)>0}-d(v)，T的總需求量為∑_{u:b(u)>0}-b(u)。虛弧的處理方式類似。4.求解：在這個(gè)擴(kuò)展后的網(wǎng)絡(luò)中，求解標(biāo)準(zhǔn)的最小費(fèi)用流問題。得到的流在原始網(wǎng)絡(luò)中即實(shí)現(xiàn)了所有供應(yīng)點(diǎn)和需求點(diǎn)的流量要求，并使總費(fèi)用最小。八、*思路：這個(gè)問題要求判斷是否存在流量值為k的流。這可以看作是在原始網(wǎng)絡(luò)流模型中，給定一個(gè)特定的流量值k作為“總供應(yīng)量”或“總需求量”來求解。這本質(zhì)上是在原始網(wǎng)絡(luò)流問題的基礎(chǔ)上增加了一個(gè)全局約束。1.模型構(gòu)建：*保持原始網(wǎng)絡(luò)G=(V,E)，弧容量c(u,v)，單位費(fèi)用e(u,v)。*目標(biāo)：找到一個(gè)流f，使得流量值為k，即∑_{v:(s,v)∈E}f(s,v)-∑_{v:(v,s)∈E}f(v,s)=k。*約束：源點(diǎn)s的總供應(yīng)量b(s)=k，匯點(diǎn)t的總需求量d(t)=k。其他點(diǎn)的凈流量為0。*容量約束：0≤f(u,v)≤c(u,v)對(duì)所有弧(u,v)∈E。*流量守恒：對(duì)所有頂點(diǎn)u≠s,t，有∑_{v:(u,v)∈E}f(u,v)=∑_{v:(v,u)∈E}f(v,u)。2.算法：*方法一：轉(zhuǎn)化為最小費(fèi)用流問題。*將此問題轉(zhuǎn)化為標(biāo)準(zhǔn)的最小費(fèi)用流形式。引入超級(jí)源點(diǎn)S和超級(jí)匯點(diǎn)T。*在弧(S,s)上設(shè)置容量c(S,s)=k，費(fèi)用e(S,s)=0。*在弧(t,T)上設(shè)置容量c(t,T)=k，費(fèi)用e(t,T)=0。*所有其他弧的容量和費(fèi)用保持不變。*求解這個(gè)標(biāo)準(zhǔn)的最小費(fèi)用流問題。如果得到一個(gè)總流量為k的流，則存在流量值為k的流；否則不存在。*方法二：基于Ford-Fulkerson算法。*使用Ford-Fulkerson算法（或其變種如Dinic、Edmonds-Karp）。*初始化流f為0。*迭代執(zhí)行：在當(dāng)前的殘留網(wǎng)絡(luò)N_f中，使用BFS或DFS尋找一條從s到t的增廣路徑P。*如果找不到這樣的路徑，則根據(jù)Ford-Fulkerson定理，當(dāng)前流f即為最大流，其流量值f*即為網(wǎng)絡(luò)的最大流值。比較f*和k：*如果f*<k，則不存在流量值為k的流（因?yàn)樽畲罅鞫夹∮趉）。*如果f*≥k，則存在流量值為k的流（最大流值至少為k，可以通過調(diào)整找到等于k的流，或者f*本身即為k）。*如果找到路徑P，計(jì)算δ=min{c_f(u,v)|(u,v)∈P}（路徑上的最小殘差容量）。*沿路徑P調(diào)整流量：f(u,v)←f(u,v)+δ對(duì)所有前向弧(u,v)∈P；f(v,u)←f(v,u)-δ對(duì)所有反向弧(v,u)∈P。*更新殘留網(wǎng)絡(luò)N_f。*復(fù)雜度分析：Ford-Fulkerson算法的時(shí)間復(fù)雜度依賴于殘差網(wǎng)絡(luò)中增廣路徑的尋找方式。如果使用基于BFS的Ford-Fulkerson（Edmonds-Karp），其時(shí)間復(fù)雜度為O(VE^2)。如果使用Dinic算法，其時(shí)間復(fù)雜度為O(V^2E)。如果網(wǎng)絡(luò)接近飽和，F(xiàn)ord-Fulkerson可能非常慢。Dinic通常更快。九、*思路：要證明這一點(diǎn)，可以從最大流-最小割定理出發(fā)，并結(jié)合殘留網(wǎng)絡(luò)的概念。1.應(yīng)用最大流-最小割定理：設(shè)網(wǎng)絡(luò)G=(V,E)中存在一個(gè)流量值為f*=C的最大流f。根據(jù)最大流-最小割定理，存在一個(gè)割(S,T)，使得f*=c(S,T)，其中S是包含源點(diǎn)s的頂點(diǎn)集，T是包含匯點(diǎn)t的頂點(diǎn)集。2.分析割的性質(zhì)：割(S,T)將網(wǎng)絡(luò)分割為兩部分，源點(diǎn)s在S中，匯點(diǎn)t在T中。割的容量c(S,T)=∑_{(u,v)∈(S,T)}c(u,v)是必須跨越S和T之間才能將流量從S送入T的“最小障礙”的總?cè)萘俊?.考慮殘留網(wǎng)絡(luò)：在最大流f下，殘留網(wǎng)絡(luò)N_f中，弧(u,v)的殘差容量為c_f(u,v)=c(u,v)-f(u,v)。4.尋找未飽和弧：如果存在一條從s到t的路徑P在殘留網(wǎng)絡(luò)N_f中，這意味著在原始網(wǎng)絡(luò)G中存在一條從s到t的路徑，使得路徑上所有弧的殘差容量c_f(u,v)>0。換句話說，對(duì)于路徑P上的所有弧(u,v)，在原始流f下，流量f(u,v)<c(u,v)。5.與割的關(guān)系：這意味著，對(duì)于路徑P上的任何弧(u,v)，其終點(diǎn)v不能在割(S,T)的集合T中。否則，如果v∈T，那么u∈S（因?yàn)镻是從s到t的路徑），那么弧(u,v)是從S指向T的割弧，其殘差容量c_f(u,v)=0。這與P的存在性矛盾。因此，路徑P上的所有頂點(diǎn)（除了可能的起點(diǎn)s和終點(diǎn)t）都必須在割(S,T)的集合S中。6.結(jié)論：既然路徑P上的所有頂點(diǎn)都在S中，那么路徑P上不存在指向T的割弧。因此，路徑P上所有弧的原始容量c(u,v)都必須小于或等于割(S,T)的容量c(S,T)。如果存在一條這樣的路徑P，那么必然有f(u,v)<c(u,v)對(duì)于所有(u,v)∈P。這表明，即使在最大流f下，也至少存在一條從s到t的路徑，其上所有弧的容量都沒有被完全飽和。十、*思路：任務(wù)分配問題可以看作是將任務(wù)（物品）分配給工人（接收者），目標(biāo)是使得完成所有任務(wù)的總時(shí)間最短。這與最小費(fèi)用流問題非常相似，因?yàn)樽钚≠M(fèi)用流問題也是要在滿足流量約束的同時(shí)，最小化某些“成本”。1.模型構(gòu)建：*頂點(diǎn)集：V={s,w_1,w_2,...,w_m,t,j_1,j_2,...,j_n}。*s：超級(jí)源點(diǎn)。*w_i：代表第i個(gè)工人，i=1,2,...,m。*t：超級(jí)匯點(diǎn)。*j_k：代表第k個(gè)任務(wù)，k=1,2,...,n。