Diskret Optimering.


13. kursusgang, tirsdag den 26. oktober 12.30-16.15


Forelæsning i G5-112 ved LKJ:

12.30-13.00: Repetition.

14.55-16.15:

Parring i ikke-todelte grafer: afsnit 10.4 og  10.5.
Introduktion til parring i vægtede grafer: afsnit 11.1 og 11.2.

Opgaveregning:

Opgave A: Lad B være den todelte graf med punktmængde {v1, ... , v10, u1, ... , u9} og med en kant mellem vi  og uj  hvis der står 1 på plads  (i,j)  i  matricen
1 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 0 1
0 0 0 0 1 0 0 1 0
0 1 1 0 0 0 0 0 1
0 0 0 0 0 0 1 0 1
0 0 1 1 1 0 1 0 0
1 0 0 0 1 0 0 0 1
0 0 0 0 1 1 1 0 0
0 1 0 0 1 0 0 0 0
1 1 0 0 0 0 0 1 0

A.1. Benyt algoritmen i afsnit  10.2  til at finde en maximum parring i B.
 
A.2. Benyt algoritmen i afsnit  10.3  til at finde en maximum parring i B.
 
Opgaver i kapitel 10: 1, 2, 3.

Afleveringsopgave for Mat5 studerende:

Opgave 2 i kapitel 10.
Besvarelser af denne opgave skal afleveres individuelt (men kun af mat5-studerende).