Diskret optimering

9. kursusgang, fredag den 13. november 8.15-12.00

8.15-8.40:

Mere om Mengers sætninger, strømninger, parringer og sammenhæng mellem disse emner.

10.40-12.00:

• Afsnit 4.3: algoritme der finder max strømning
• Afsnit 4.4: hurtig algoritme der finder max strømning

Opgaveregning:

• Opgave 4.1
• Opgave 4.2
• Lad D=(V,A) være et netværk hvor s,t er to punkter og med kapacitetsfunktion c.
  Lad δ^out(U₁)  og  δ^out(U₂) være s-t snit med minimal kapacitet.
  Vis at  δ^out(U₁ ∩ U₂)  og  δ^out(U₁ ∪ U₂) er s-t snit med minimal kapacitet.