Diskret optimering - 7

7. kursusgang, mandag den 25. september 12.30-16.15

12.30-13.00:

Mere om max vægt parringer i todelte grafer og LP.

14.55-16.15:

• Afsnit 8.1: introduktion til heltals LP
• Afsnit 8.2: hvornår er den optimale løsning til et LP heltallig.
  Kun side 136-137 og (uden bevis:) Korollar 8.2a
• Afsnit 8.3: parringer i todelte grafer.
  

Opgaveregning:

1. Opgave 3.23 (i).
2. Sætning  3.7 er ifølge bogen en "extension of Kőnig's matching theorem (Theorem 3.3)".
   Forklar hvorfor Kőnigs sætning er et specialtilfælde af  Sætning 3.7.
3. Vis at  P_{perfect matching}  er en delmængde af  { x \in R^E |   x>=0,  Ax = 1}.   Dette  er den nemme del  af Sætning  3.6.
4. Opgave  3.26.