Diskret optimering - 18

18. kursusgang, torsdag den 9. november 8.15-12.00

8.15-8.45:

Eksempler på matroider. Dualitet og anvendelse.

10.40-12.00:

• Afsnit 10.4 og 10.5: algoritme, der finder en største mængde der er uafhængig i to forskellge matroider.
• Anvendelse af algoritmen.
  

Opgaveregning:

Algoritme, der finder max. vægt basis i en matroide M med vægtfunktion w.

B:=Ø,   B*:=Ø,  Z:=X
while Z<>Ø:
    if der findes en kreds C i M, hvor C delmængde af B \cup Z then lad x have mindst vægt i C, Z:=Z-x, B*:=B*+x
   else lad C kreds i M*, hvor er delmængde B* \cup Z, lad x have størst vægt i C, Z:=Z-x, B:=B+x,

{B er max. vægt basis for M og B* er min. vægt basis for M*}

1. Anvend algoritmen på opgave 1.7
2. Vis x er i Z. Vis at algoritmen standser med de ønskede baser. 
3. Opgave 10.16