|  |
01527 Videregående grafteori |
| | |  | Engelsk titel:
| Graph Theory II | Sprog:
| | Point
(ECTS )
| 5 | Kursustype:
| Ph.D.- Matematik, Fysik og Informatik
| | Kurset udbydes under åben uddannelse |
| | |
| Skemaplacering:
| E1B
| Undervisningsform: | To timers forelæsning efterfulgt af to timers grupperegning | Kursets varighed:
| 13-uger | Eksamensplacering:
| Aftales med læreren
Eksamenstidspunktet aftales med de studerende | Evalueringsform:
| | Eksamens varighed:
| | Bedømmelsesform: | | Obligatoriske forudsætninger: | | Faglige forudsætninger: | | Ønskelige forudsætninger: | |
| Deltagerbegrænsning: | Minimum 8, Maksimum: 100 | | | Overordnede kursusmål:
| Kurset vil indeholde en række klassiske grafteoretiske resultater, såsom sætningerne af Tutte, Ramsey, Turan, Kuratowski,
Brooks, Dirac, Smith, og Vizing, samt Jordan's kurvesætning. Desuden vil mere moderne problemstillinger, såsom liste-farvninger, blive gennemgået. |
| Læringsmål: | | En studerende, der fuldt ud har opfyldt kursets mål, vil kunne: | - Anvende frembringerfunktioner
- Anvende tælleteknik, illustreret med Ramsey's sætning
- Anvende grundlaget for plane grafer: Jordan's kurvesætning
- Anvende Kuratowski 's planaritetssætning
- Beherske de klassiske sætninger af Turan, Brooks, Dirac, Smith og Vizing.
- Anvende algebraiske metoder illustreret ved det kromatiske polynomium
- Anvende liste-farvningsmetoden
- Forstå implikationerne af stor minimumvalens
| Kursusindhold:
| 1.Frembringerfunktioner, Catalan-tallene.
2.Tutte’s 1-faktorsætning. Petersen’s sætning.
3.Sætningerne af Ramsey og Turan.
4.Jordan’s kurvesætning.
5.Kuratowski’s sætning om plane grafer.
6.Hamilton kredse. Dirac’s sætning og Grinberg-kriteriet.
7.Antal hamilton kredse (Smith’s sætning) samt kromatisk tal og maksimalvalens (Brooks’ sætning).
8.Vizing’s sætning om kantfarvning.
9.Kromatisk polynomium.
10.Liste-farvning. 5-farvning af plane grafer.
11.Grafer med stort kromatisk tal og ingen små kredse.
12.Mader’s resultater om implikation af stor minimumvalens.
|
| Kursusansvarlig:
| , 322, 008, (+45) 4525 3058,
| Institut:
| 01 Institut for Matematik | Tilmelding:
| I CampusNet |
|
|
| | Sidst opdateret:
17. juli, 2012 |
Åbn kurset i Kursusbasen
|