Diskret optimering - 17

17. kursusgang, mandag den 6. november 12.30-16.15

12.30-13.00:

Mere om matroider, eksempler på matroider.

14.55-16.15:

• Afsnit 10.3: eksempler på matroider.
• Afsnit 10.2: ækvivalente definitioner af matroider.
• Afsnit 10.4 og 10.5: vi skal beskrive en algoritme der finder en max. vægt mængde der er uafhængig i to forskellige matroider (på samme mængde X). I dette afsnit ser vi kun på vægt w=1 (altså max. kardinalitet af mængden). Beviset for algoritmen (herunder afsnit 10.4) når vi nok ikke denne gang.
  

Opgaveregning:

1. Opgave 10.2
2. Opgave 10.4
3. Opgave 10.18 (i) og (ii)