【網絡流】最大流：求最小割值、求（邊）不交路徑數量、求二分比對最大比對數

1）最大流等于最小割：

P249，定理7.13，每個流網絡中，一個s-t 流的最大值等于一個s-t 割的最小容量。

即，求s-t 的最小割，可以轉換為求 s-t 的最大流。

2）有向圖和無向圖中的 （邊）不相交路徑：

說一組路徑邊不相交，指所有路徑不共享任何一條邊，但是可以共享節點。

有向邊不交路徑問題是，在有向圖G中找到邊不交的 s-t 路徑的最大數目；無向邊不交路徑問題是，在無向圖G中找到邊不交的 s-t 路徑的最大數目。

P267，命題7.41，如果在有向圖G中從 s 到 t 存在 k 條邊不交的路徑，那麼G中的最大 s-t 流的值至少是 k。

根據命題，我們把G中的所有邊的容量設為 1 ，那麼很明顯，G中的最大 s-t 流的值若為 f ，那麼G中從 s 到 t 就會存在 f 條邊不交的路徑！

即，求 s-t 的邊不相交路徑，可以轉換為求 s-t 的最大流（需要把G的邊全部設為 1）。

3）二分比對問題（在一個圖G中，找一個最大規模的比對，不一定是完美比對）：

P263，定理7.37，G中最大比對的大小等于G‘最大流的值；并且G中這樣一個比對中的邊就是G’中從X到Y的攜帶流的邊。

即，求G的最大二分比對數，可以轉換為G的最大流（需要把G的邊全部設為 1，并且加超級源點和彙點）。

一個圖G，如果不具有完美比對，直覺感受是：能找到任意的一個節點集合V，V的鄰居節點的集合NV含有的節點數量少于V含有的節點數量，即 | NV |<| V | 。