MM10 Grafteori FALL 2006 (instructor Bjarne Toft)

MM10 NEWS NO. 14 (December 13, 2006)

The image “http://www.mathpuzzle.com/petersen.gif” cannot be displayed, because it contains errors.

The Petersen Graph in several different ways, exhibiting some of its symmetries.

The lecture on Wednesday Dec. 13, 2-4 PM, deals with Chapter II in the red book (Bjarne Toft: Algoritmisk Kombinatorik, Matematiklærerforeningen 1985 og SDU 2005), in particular:

The job-assignment problem and the Hungarian Algorithm
LP duality (3 pages with a very simple proof of the duality theorem will be distributed)
The primal-dual solution method for LP
Shortest paths and the primal-dual method

The exercises on Monday Dec. 18 will be a lecture dealing with:

Chapter III in the red book (NP- and NPC-problems)

The lecture on Wednesday Dec. 20 has unfortunately been cancelled (due to BT being external examiner for a 'speciale' at KU). A final class on Dec. 21 will be discussed on Dec. 13 and 18.

Tilmeldte til eksamen: Jacob, Nicolai, Mia, Vagn, Thomas, Jens, Lasse, Kirsten, Per. (Annegrethe er IKKE tilmeldt på den officielle liste). Foreløbig aftalte projekter: Jacob: Hamilton Kredse i Grafer ; Mia: Turans Sætning og Extremalteori ; Lasse: Ruteproblemer i grafer, specielt det Kinesiske Postbud ; Kirsten : Hamilton Kredse i Grafer ; Per : Punktfarvning af Grafer ; Annegrethe : Grafer som er k-kromatiske, men uden Korte Kredse ; Vagn (får et projekt, men melder muligvis fra) ; Jens (Strømning og cirkulation i netværk med anvendelser på grafer). Evt. ønsker om ændringer i disse foreløbige aftaler kan I evt. bringe frem. Følgende er der endnu ikke lavet aftale med : Nicolaj, , Thomas.