TATA64 · 6 hp · Avancerad nivå (A1N) · Matematik, Tillämpad matematik
Grafteori
Ges · nästa start VT 2027
100 %
klarade senaste ordinarie tillfället
UPG1 · 28 maj 2026 · 14 studenter
100 %
klarade de ordinarie tillfällena, alla tillfällen de senaste 5 åren
UPG1 · 58 studenter
Modulen rapporterar bara godkända resultat, så andelen godkända visar inte hur många som inte klarade den.
Ingår i 7 program
Inlämning eller laboration
UPG1 Inlämningsuppgifter
- 5
- 4
- 3
Ordinarie tillfällen
100 % godkända · 58 studenter
- 100 %14
- 100 %10
- 100 %22
- 100 %12
Senare tillfällen
Inga tillfällen med minst 5 studenter.
- Får 4 eller 5: 38 % (58 studenter)
Visa små tillfällen (1)
Tillfällen med färre än 5 studenter, ofta tillgodoräknanden eller specialtillfällen. De ingår inte i någon siffra på sidan.
- 100 %1
Om kursen
Mål
Kursen syftar till att ge en grundlig kännedom om grafteoretiska begrepp och förmåga att använda dem inom matematik, naturvetenskap och datavetenskap. Efter fullgjord kurs skall studenten
- känna till viktiga klasser av grafteoretiska problem,
- kunna formulera och använda centrala satser om träd, matchningar, konnektivitet, färgningar samt planära och hamiltonska grafer,
- kunna beskriva och tillämpa några grundläggande algoritmer för grafer,
- ha kännedom om elementär Ramseyteori,
- kunna lösa enkla grafteoretiska problem och använda grafteori som verktyg vid modellering.
Innehåll
- Träd: Cayleys formel och uppspännande träd
- Konnektivitet och Mengers sats
- Matchningar och övertäckningar, Tuttes sats om perfekta matchningar, Egervarys algoritm
- Hamiltoncykler och färgningar av grafer
- Elementär Ramseyteori
- Plana grafer: Eulers formel, femfärgssatsen
- Några tillämpningar inom naturvetenskap, schemaläggningar och datavetenskap
- Examinator
- Carl Johan Casselgren
- Schemalagd tid
- 48 h
- Huvudområde
- Matematik, Tillämpad matematik