完整性定理最大流量

Question

的integraloty定理告訴我們，如果在流動網絡中的所有能力都是整數，再有就是，每一個值是一個整數

但最顯着的部分是一個最大流量存在，不是每個最大流量！ 這意味着這一說法並不要求每最大流量爲整數值

我想不出爲什麼如果所有的容量是整數，但存在一個最大流量不整數值！

或者我剛剛弄錯了這個試圖告訴我的定理的想法嗎？

Answer 1

如果使用福特富爾克森方法來獲取最大流量，則導致流必須是整數值

但是，我們仍然可以使用實數作爲邊緣

流量值最大流量

檢查這個例子：

  B 
     / \ 
    / \ 
    /  \ 

小號------甲噸

 \  /
     \ /
     \ /
      C 

邊的方向全部從左到右，（s，a）有1個流量和1個容量，其餘全部都是0.5個流量和1個容量。

這是具有最大流量但不是整數值的流量網絡。

Answer 2

讓

• E =在圖形邊緣。
• C（E）=在給定邊e
• F（E）的容量=流的量，通過給定邊e去

該定理指出：

如果。（E ）對於所有邊，e中的圖是整數，則存在最大流量f，其中每個流量值f（e）是整數。

通知定理不到位約束上F（E）。

只有c（e）必須是整數。
由於「c（e）必須是整數」並不意味着「f（e）必須是整數」。
因此，具有整數容量的非整數流是完全有效的。

下面是一個示例，其中所有容量都是具有一些邊緣具有非整數流量的最大流量的整數。

G是流圖我正在與工作.. N是最大積分流量.. N`是它有一些邊緣具有非整數流程的最大流量..上

對數邊緣格式：「流/容量」

記住定理只是說上限的F（U，v）的整數..它並沒有說明其下界什麼。因此流量可以是介於0和c（u，v）之間的任何數字。