or教案23_圖論-文庫吧
2025-09-15 15:13 本頁面
【正文】 定義 3 設(shè) f 是一個(gè)可行流 , 181。 是從 vs 到 vt 的一條鏈 ,若 181。滿 足下列條件 ,稱之為 (關(guān)于可行流 f 的 )一條增廣 鏈。 (vi , vj ) ∈ 181。 0 fij ≤ cij 后向弧 是非零流弧， (vi , vj ) ∈ 181。+ 0≤ fij cij 前向弧是 非飽和弧， v1 v2 v3 v4 v5 v6 4. 截集與截量 設(shè) S， T?V， S?T= ? ，始點(diǎn)在 S，終點(diǎn)在 T中的所有 弧的集合 ，記為（ S， T）。 S T 定義 4 網(wǎng)絡(luò) D=(V,A,C） ,若點(diǎn)集 V被剖分為兩個(gè)非空集 合 V1和 V1,使 vs∈ V1， vt ∈ V1，則把弧集 (V1， V1) 稱為是分離 vs和 vt的截集。 v2 v5 v3 v1 v4 v6 =(v1,v2,v3) V1 V 1=(v4,v5,v6) 定義 5 給一截集（ V1， V1），把截集（ V1， V1）中所 有弧的容量之和稱為這個(gè)截集的容量（簡(jiǎn)稱為截 量），記為 C （ V1， V1）， 即 ???)V,(V),(1111)V,C ( V ji vvijc 不難證明，任何一個(gè)可行流的流量 V( f )都不會(huì) 超過任一截集的容量。即 )V,C ( VV ( f ) 11?可行流 f *，截集 (V1*， V1*), 若 V( f *)=C( V1*， V1*）， 則 f *必是最大流， (V1*， V1*) 必是 D的最小截集。 定理 1 可行流 f *是最大流，當(dāng)且僅當(dāng)不存在關(guān)于 f * 的增廣鏈。 證明：若 f *是最大流，設(shè) D中存在關(guān)于 f *的增廣鏈 181。， 由增廣鏈的定義，可知 ? 0,令 ??????????????uvv fuvvfuvvffji*ijji*ijji*ij**ij ),( ),( ),( ??不難驗(yàn)證， 是一個(gè)可行流 ,且 ? ?** jif? = min ???????*iju*ijijuffc m i n , )(m i n 令 )V( θ)V( )V( **** fff ???這與 f *是最大流的假設(shè)矛盾。 設(shè) D中不存在關(guān)于 f *的增廣鏈，證明 f *是最大流。 定義 V1 * ，令 vs∈ V1*, 若 vi∈ V1*,且弧 (vi,vj)上 , fij*cij, 則令 vj∈ V1*, 若 vi∈ V1*,且?。?vj， vi）上 , fji*0，則令 vj∈ V1*。 因?yàn)椴淮嬖陉P(guān)于 f *的增廣鏈，故 vt ∈ V1*， 記 V1*=V\ V1*，得截集（ V1*， V1*），顯然有 ????????),vv),vv cfjijiij*ij*1*1*1*1V V(),( 0 V (V),(
外語相關(guān)推薦
鄂ICP備17016276號(hào)-1