Diskret optimering - 18


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


Forelæsning i G5-109:

8.15-8.45:

Eksempler på matroider. Dualitet og anvendelse.

10.40-12.00:


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