MM10  Grafteori  EFTERÅR 2006 (underviser Bjarne Toft).

Updated Dec. 18, 2006.

The lecture Wednesday Dec. 20 is cancelled!

The lecture on Monday Dec. 18 will be the final meeting of the class.


Link to News No.1
Link to News No.2
Link to News No. 3 and 4
Link to News No. 5
Link to News No. 6 
Link to News No. 7
Link to News No. 8
Link to News No. 9
Link to News No. 10
Link to News No. 11
Link to News No.12
Link to News No. 13
Link to News No. 14
Link to News No. 15

There are weekly classes MONDAY 10- 12 in the seminar room and WEDNESDAY 14-16 in the seminar room.

We use the following book (in Danish!) :
Bjarne Toft: Algoritmisk Kombinatorik, Syddansk Universitet 2005.


*****************************************************************
Course material:

Bjarne Toft, Algoritmisk Kombinatorik - et datalogisk orienteret emne i
matematik, Matematiklærerforeningen 1985, genoptryk SDU 2005, 127 sider.

PRÆMIEOPGAVE, Notes in Danish and English, 30 pages.

Lovász L., Three short proofs in graph theory, J. Combinatorial Theory B19
(1975), 269-271.

Connectivity in graphs: Menger's Theorem and Ford-Fulkerson's Algorithm. Notes. 16 pages.

Network flows; Ford and Fulkerson, Notes, 7 pages.

B.Toft, Uløste grafteori problemer (Unsolver Graph Theory Problems), 13 pages.

Turan's Theorem, 25 pages.

Hamiltonian Cycles, 20 pages.

Notes on Vertex Colourings, 27 pages.

Edge-colouring problems, 22 pages.

Trær (West, Sachs, Stiebitz), 21 pages

LP dualitet, 3 pages

****************************************************************

Tilmeldte til eksamen: Jacob, Nicolai, Mia, Vagn, Thomas, Jens, Lasse, Kirsten, Per. (Annegrethe er IKKE tilmeldt på den officielle liste). Aftaler om eksamensprojekter aftales i december, se News 15.


Possible exam projects (Danish titles) :

  1. Skemalægning og grafteori

  2. Ruteproblemer (Euler's Sætning)

  3. Hamilton kredse

  4. Travelling Salesman

  5. Det kinesiske postbud

  6. Trær

  7. Pardannelse i 2-delte grafer (König's og Hall's Sætninger)

  8. Pardannelse i generelle grafer (Tutte's og Petersen's Sætninger)

  9. Faktorisering af grafer

  10. Jobtilordningsproblemet

  11. LP-dualitet og grafteori

  12. Max-min sætninger i grafteori

  13. Kant-farvning (Vizing's Sætning)

  14. Punkt-farvning (Brooks' Sætning)

  15. Farvning af plane grafer

  16. Ekstremal grafteori (Turan's Sætning)

  17. Sammenhæng i grafer

  18. Menger's saetning

  19. Gode saetninger og gode algoritmer i grafteori

*******************************************************************

This page has address:
http://www.imada.sdu.dk/~btoft/MM10/

It may also be obtained via Blackboard.