Cut ·Digraph:D(V,E) ·source:s∈V sink:t∈V ·Capacity c:E→R0·Cut ScV,s∈S,ttS 0/1 0/1 0/1 0/1 0/3 0/3 0/4 ,0/1 0/1 。Value of cut: Σ Cuv u∈S,v庄S,(u,v)∈E
• Digraph: • Capacity D(V, E) c : E → ℝ≥0 Cut 0/1 0/4 0/1 0/1 0/1 0/1 0/1 0/4 0/3 0/3 s t • source: sink: • Cut , , s ∈ V t ∈ V S ⊂ V s ∈ S t ∉ S • Value of cut: ∑ u∈S,v∉S,(u,v)∈E cuv
Minimum Cut ·Digraph:D(V,E) ·source:S∈V sink:t∈V ·Capacity c:E→R≥o ·Cut SCV,S∈S,t庄S 0/1 0/1 0/3 0/3 0/4 0/1 。Value of cut: Σ Cuv u∈S,v庄S,(u,v)∈E
• Digraph: • Capacity D(V, E) c : E → ℝ≥0 Minimum Cut 0/1 0/4 0/1 0/1 0/1 0/1 0/1 0/4 0/3 0/3 s t • source: sink: • Cut , , s ∈ V t ∈ V S ⊂ V s ∈ S t ∉ S • Value of cut: ∑ u∈S,v∉S,(u,v)∈E cuv
Fundamental Theorem of Flow .Flow network:D(V,E),s,t∈V,andc:E→R≥o 。Max-flow=min-cut 。With integral capacity c:E→Z≥o,the maximum flow is achieved by an integer flow f:E→Z≥o 0/1 0/1 0/1 0/1 0/3 S t 0/3 0/4 0/1 0/4 0/1
• Flow network: , , and • Max-flow = min-cut • With integral capacity , the maximum flow is achieved by an integer flow . D(V, E) s, t ∈ V c : E → ℝ≥0 c : E → ℤ≥0 f : E → ℤ≥0 Fundamental Theorem of Flow 0/1 0/4 0/1 0/1 0/1 0/1 0/1 0/4 0/3 0/3 s t
Fundamental Theorem of Flow .Flow network:D(V,E),s,t∈V,andc:E→R≥0 ·Max-flow=min-cut 、With integral capacity c:E→Z≥o,the maximum flow is achieved by an integer flow f:E→Z≥o- 0/1 01 0/1 0/3 S 0/3 0/4 0/1
• Flow network: , , and • Max-flow = min-cut • With integral capacity , the maximum flow is achieved by an integer flow . D(V, E) s, t ∈ V c : E → ℝ≥0 c : E → ℤ≥0 f : E → ℤ≥0 Fundamental Theorem of Flow s t 0/1 0/4 0/1 0/1 0/1 0/1 0/1 0/4 0/3 0/3
Fundamental Theorem of Flow .Flow network:D(V,E),s,t∈V,andc:E→R≥0 。Max-flow=min-cut 。With integral capacity c:E→Z≥o,the maximum flow is achieved by an integer flowf:E→Z≥o- 0/1 1/1 1/1 2/3 S 23 314 1/1 3/4 01
• Flow network: , , and • Max-flow = min-cut • With integral capacity , the maximum flow is achieved by an integer flow . D(V, E) s, t ∈ V c : E → ℝ≥0 c : E → ℤ≥0 f : E → ℤ≥0 Fundamental Theorem of Flow s t 1/1 3/4 0/1 1/1 1/1 0/1 1/1 3/4 2/3 2/3