Diskret optimering - 10

10. kursusgang, torsdag den 5. oktober 8.15-12.00

8.15-8.45:

10.40-12.00:

• Afsnit 4.3: Strømning i netværk
• Afsnit 4.4:  Algoritme der finder max strømning. 
• Måske lidt af afsnit 4.5.
  

Opgaveregning:

1. Lad G være den todelte graf med punktmængde {u₁, ... , u₁₀, w₁, ... , w₉} og med en kant mellem u_i  og w_j  hvis der står 1 på plads  (i,j)  i  matricen
   
   
   1 0 0 0 1 0 0 0 1
   1 0 0 1 0 0 0 0 1
   0 0 0 0 1 0 0 1 0
   0 1 1 0 0 0 0 0 1
   0 0 0 0 0 0 1 0 1
   0 0 1 1 1 0 1 0 0
   1 0 0 0 1 0 0 0 1
   0 0 0 0 1 1 1 0 0
   0 1 0 0 1 0 0 0 0
   1 1 0 0 0 0 0 1 0
   
   

   Benyt algoritmen beskrevet i afsnit 4.2  (Corollary 4.5a) til at finde en maximum parring i G.