Diskret optimering
15. kursusgang, fredag den 4. december 8.15-12.00
Forelæsning i G5-109:
8.15-9.00:
Matroider og den grådige algoritme.
Opgaveregning:
- Vis at den grådige algoritme kan bruges til at finde en minimum vægt basis for en matroide.
- Opgave 10.13 (Y=F)
- Opgave:
Betragt den vægtede komplette graf med punktmængde: {Apeldoorn, Arnhem,
Assen, Bergen op Zoom, Breda, Eindhoven,Enschede, 's Gravenhage} hvor
vægten af en kant er afstanden mellem de to byer den forbinder, se
tabel side 22. Find en delgraf med højst én kreds og med størst mulig
vægt.
Afleveringsopgaver.