Enkeltfag Engelsk 5 ECTS

Videregående grafteori

Overordnede kursusmål

Kurset vil indeholde en række klassiske grafteoretiske resultater, såsom sætningerne af Tutte, Ramsey, Turan, Kuratowski,
Brooks, Dirac, Smith, Vizing, Roy-Gallai, Camion og Robbins samt Jordan’s kurvesætning. Desuden vil mere moderne problemstillinger, såsom liste-farvninger, blive gennemgået.

See course description in English

Læringsmål

  • 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, Vizing, Roy-Gallai, Camion og Robbins.
  • Anvende liste-farvningsmetoden.
  • Anvende algebraiske metoder illustreret ved det kromatiske polynomium.
  • Forstå den probabilistiske metode illustreret med grafer med stort kromatisk tal og uden korte kredse.

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.Liste-farvning.
10.Kromatisk polynomium.
11.Orienterede grafer.
12.Grafer med stort kromatisk tal og ingen små kredse.

Anbefalede forudsætninger

Undervisningsform

To timers forelæsning efterfulgt af to timers grupperegning

Fakultet

Pladsbegrænsning

Minimum 6, Maksimum: 100.

Vær opmærksom på, at dette enkeltfagskursus har et minimumskrav til antal deltagere. Derudover er der begrænsning på antallet af studiepladser. Er der for få tilmeldinger oprettes kurset ikke. Er der for mange tilmeldinger, vil der blive trukket lod om pladserne. Du får besked om, om du har fået tildelt en studieplads senest 8 dage før kursusstart.

Se kurset i kursusbasen

Tilmelding

Sprog

Engelsk

Varighed

13 uger

Institut

Compute

Sted

DTU Lyngby Campus

Kursus ID 01527
Kursustype Ph.d.
Semesterstart Uge 35
Semester slut Uge 48
Pris

10.600,00 kr.

Vær opmærksom på dette kursus har deltager begrænsninger. Læs mere

0 pladser tilbage

Tilmelding