Diskret Optimering.

16. kursusgang, tirsdag den 9. november 12.30-16.15

Forelæsning i G5-110 ved LKJ:

12.30-13.00: Repetition.

14.55-16.15:

Afsnit 12.1, 12.2, 12.3 om tre forskellige algoritmer, der finder minimum/maximum vægt udspændende træ.
Afsnit 12.4 om matroider - om en generelisering af udspændende træer.

Opgaveregning:

Opgaver i kapitel 11: 4, 3, 5(b)

Opgave A:
Betragt følgende grådige algoritme, der som input får en komplet graf med lige antal punkter og med vægte på kanterne:
M:=Ø
while |M|<|V|/2 do
begin
lad e være en kant med mindst vægt i grafen;
if e ikke er incident med et punkt, som også er incident med et punkt i M then tilføj e til M;
fjern e fra grafen
end
Finder denne algoritme en minimum vægt parring i grafen ?