TATA64 Grafteori 2011

studiehandbok@lith

Tekniska högskolan vid Linköpings universitet

År : 2011

TATA64	Grafteori, 4 p / 6 hp /Graph Theory/ För: CS D IT MMAT
OBS!	Vartannatårskurs, ges 2011.
	Prel. schemalagd tid: 36 Rek. självstudietid: 124
	Utbildningsområde: Naturvetenskap Ämnesgrupp: Matematik Nivå (A-D):C 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 och Edmonds algoritm för isomorfi Konnektivitet och Mengers sats, blocker 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, Grinbergs formel Några tillämpningar inom naturvetenskap, schemaläggningar och datavetenskap
	Kurslitteratur: J.A.Bondy and U.S.R. Murty, Graph theory Springer, 2008.
	Examination:
TEN1	Skriftlig tentamen (U,3,4,5)	6 hp

Undervisningsspråk är Engelska.
Institution: MAI.
Studierektor: Ulf Janfalk
Examinator: Armen Asratian
Ansvarig programnämnd: Data&Medie

Engelsk kursplan

Kursen bedrivs på ett sådant sätt att både mäns och kvinnors erfarenhet och kunskaper synliggörs och utvecklas.

Planering och genomförande av kurs skall utgå från kursplanens formuleringar. Den kursvärdering som ingår i kursen skall därför genomföras med kursplanen som utgångspunkt.

Om inget annat anges ovan gäller betygsskala enligt avsnitt a8.5 i de gemensamma bestämmelserna.

Kursplanen gäller för 2011 enligt beslut av ansvarig programnämnd/fakultetstyrelse.

Tekniska högskolan vid Linköpings universitet
Informationsansvarig: TFK , val@tfk.liu.se Senast ändrad: 04/29/2011