Diskret optimering

7. kursusgang, torsdag den 5. november 8.15-12.00

8.15-8.40:

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

10.40-12.00:

• 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 8.1
2. Opgave 8.3
3. Korollar 3.7b og Sætning  3.8 er ifølge bogen "extension of Kőnig's matching theorem (Theorem 3.3)".
   Forklar hvorfor Kőnigs sætning er et specialtilfælde af  Sætning 3.8.
4. 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.
5. Opgave  3.26.