Diskret optimering - 6

6. kursusgang, torsdag den 21. september 8.15-12.00

8.15-8.45:

Mere om parring. Specielt korollarer til Kőnigs sætning.
Korollar 1 (Hall).
Hvis G er en todelt graf med punktmængder U og W
så har G en parring med |U| kanter hvis og kun hvis
for alle delmængder S af U gælder: |N(S)| >= |S|,
hvor N(S) er mængden af punkter i W, der er nabo til et punkt i S.

Korollar 2: Opgave 3.11.

10.40-12.00:

• Resten af afsnit 3.5: en algoritme, der finder max vægt parring i todelt graf.
• Afsnit 3.6: Parring og lineær programmering.

Opgaveregning:

1. Opgave 3.17
2. Gennemgå Application 3.1.
   Opgave 3.18
3. Opgave 3.2
4. Opgave 3.4
5. Opgave 3.5