TATA64 · Linköpings universitet
Grafteori
Ny kurs
Inga tentor än
Ladda upp dina tidigare tentor och få hjälp med att strukturera ditt studiematerial
Få dina tentauppgifter kategoriseradeBli guidad genom ditt studiematerialFå hjälp direkt med teori och tipsHåll koll på dina framsteg
HP
6
Språk
Engelska
Nivå
Avancerad nivå
Fakultet
Tekniska fakulteten
Institution
Matematiska institutionen
Lärandemå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.
Kursinnehå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
Förutsättningar
- Grundkurser i linjär algebra och diskret matematik.
Litteratur
Graph theory with applications (tillgänglig via internet) - J.A.Bondy, U.S.R. Murty
Graph Theory (tillgänglig via internet) - R. Diestel
Kompletterande material som utdelas under kursens gång
Liknande kurser vid andra universitet
Gör som 15 000+ studenter och ta kontroll över ditt tentaplugg.
Kom igång gratis