| TATA64 |
Grafteori, 6 hp
/Graph Theory/
För:
CS
D
DAV
IT
Mat
MMAT
U
|
OBS! |
Vartannatårskurs. Ges 2017
|
| |
Prel. schemalagd
tid: 48
Rek. självstudietid: 112
|
| |
Utbildningsområde: Naturvetenskap
Huvudområde: Matematik, Tillämpad matematik Nivå (G1,G2,A): A
|
| |
Datavetenskap Matematik, diskret matematik
|
| |
Mål:
IUAE-matris
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 bevisa centrala satser om träd, matchningar, konnektivitet, färgningar, plana och hamiltonska grafer
- kunna beskriva och tillämpa några grundläggande algoritmer för grafer
- ha kännedom om elementär Ramseyteori
- kunna använda grafteorin som verktyg vid modellering
|
| |
Förkunskaper: (gäller studerande antagna till program som kursen ges inom, se 'För:' ovan)
Grundkurser i linjär algebra och diskret matematik.
OBS! Tillträdeskrav för icke programstudenter omfattar vanligen också tillträdeskrav för programmet och ev. tröskelkrav för progression inom programmet, eller motsvarande.
|
| |
Organisation:
Föreläsningar och lektioner.
Kursen pågår hela vårterminen.
|
| |
Kursinnehåll:
- Träd: Cayleys formel, 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
|
| |
Kurslitteratur:
J.A.Bondy and U.S.R. Murty, Graph theory with applications (tillgänglig vid internet)
R. Diestel, Graph Theory, 4th ed., 2010 (tillgänglig vid internet)
Samt kompletterande material som utdelas under kursens gång.
|
| |
Examination: |
TEN1
|
Skriftlig tentamen (U,3,4,5)
|
6 hp
|
| |
|
|