MM10 Grafteori FALL 2006 (instructor Bjarne Toft)

MM10 NEWS NO. 13 (December 6, 2006)

The Petersen Graph on the beach! Or rather a graph related to the Petersen Graph :

This is the Austrian graph theorist Herbert Fleischner who (among many other things) wrote books on Euler's theorem:
Herbert Fleischner, Eulerian Graphs and Related Topics, Part 1, Volumes 1 and 2, Annals of Discrete Mathematics 45 and 50, North-Holland 1990 and 1991

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

The Chineese Postman (related to this is the Shortest Path Problem and the Weighted Matching Problem)
The Travelling Salesman (related to a heuristic algorithm for this is the Minimum Spanning Tree Problem and the Weighted Matching Problem)

The exercises on Monday Dec. 11 will deal with:

Exercises from Chapter I in the red book.

The lecture on Wednesday Dec. 13, 2-4 PM, will deal with Chapter II in the Red Book.
The lecture on Wednesday Dec. 20, 2-4 PM, will deal with Chapter III in the Red Book.

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: Ruteproblemet for det Kinesiske Postbud ; Kirsten : Hamilton Kredse i Grafer ; Per : Kantfarvning af Grafer ; Annegrethe : Grafer som er k-kromatiske, men uden Korte Kredse. Evt. ønsker om ændringer i disse foreløbige aftaler kan I evt. bringe frem. Følgende er der endnu ikke lavet aftale med : Nicolaj, Vagn, Thomas, Jens.