1. 問題1：網(wǎng)絡(luò)流是模型而不是問題，這是什么樣的模型？

1.1 模型

1.2 兩個約束：

• 容量約束:每條鏈路上的流量不超過容量;
• 流約束：中間節(jié)點不存儲流、從起點到達(dá)終點;除了起點和終點，流入多少，流出多少；

2. 最大流問題

2.1 問題描述

• 給定一個圖，一個起點，一個終點，找到一條從起點到終點的路徑，使得流的大小最大；

2.2 Ford-Fulkerson 算法

2.2.1 核心過程

• 找到一條路徑：從起點出發(fā)，向前走，直到到達(dá)終點；
• 構(gòu)建 residual graph：根據(jù)最新找到的最大流，更新 residual graph，構(gòu)建反向路徑；
• 重復(fù)上述過程，直到無法找到一條可行路徑；

2.2.2 算法分析

• 為什么輸出為最大流：一旦算法停止，節(jié)點被分為兩個集合，也就是一個集合的割集，算法停止的時候就是最小割的解，而最大流的上界和最小割的下界碰到一起就是最優(yōu)解；

3. 為什么這個算法是正確的，這是不是多項式算法？

問題的正確性證明：對偶問題 - “最小割集”

3.2關(guān)于復(fù)雜性的討論；

• 什么條件下，循環(huán)會結(jié)束？答：節(jié)點被分為兩個集合；
• 每次循環(huán)向 “終點” 逼近多少？答：至少前進(jìn)一個整數(shù)；
• 終點有多遠(yuǎn)該如何理解？
• 算法是否為多項式取決于什么？

4. 癥結(jié)在哪里？如何克服？

• 癥結(jié)：每次增加的流的大小很?。?/li>
• 克服：每次選擇一個足夠的增量（不大于容量總和），循環(huán)找，直到找不到了；找不到了，則將增量除以2；

我的問題：為什么是最小割？
問題：最大流是一個P問題，而不是一個NPC問題；為什么？

問題6：正確性沒有問題，為什么？如何能肯定效率改進(jìn)了？

將外層循環(huán)，稱為 scaling phase。
加入可以知道：

• 外循環(huán)次數(shù)：-scaling phase 個數(shù)的上限（即用到的不同數(shù)量的上限）；log2()；
• 內(nèi)循環(huán)的次數(shù)：任一phase 中執(zhí)行augment次數(shù)；

問題7. 為什么知道最優(yōu)解多遠(yuǎn)最關(guān)鍵？

換句話說：網(wǎng)絡(luò)中的最大流值不大于 v(f)+m
證明方法：最小割的最大值，不超過v(f)+m。

問題8：這仍然不是傳統(tǒng)圖意義上的多項式算法。試圖實現(xiàn) “那種” 意義上多項式算法的思想完全不同于augment的思想。你能理解關(guān)鍵的差異嗎？

• Prim：過程中間結(jié)果始終滿足 “可行解”的要求，但未必滿足 “最小” 要求，在過程中不斷 “修正” 目標(biāo)值，一旦找到 “終點”，即最小可行解。
• Kruskal：過程中間結(jié)果不具備 “可行解”特征，卻體現(xiàn) “最小” 的要求，一旦構(gòu)成可行解，即為最優(yōu)解。