studiehandbok@lith   Länk till universitetets hemsida
 

Tekniska högskolan vid Linköpings universitet

Sök

 Länk till universitetets hemsida
 
År : 2013
 
TATA64 Grafteori, 4 p / 6 hp
/Graph Theory/

För:   CS   D   DAV   IT   MMAT  


OBS!
Vartannatårskurs, ges 2013
 

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
  • 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 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
 


Undervisningsspråk är Engelska.
Institution: MAI.
Studierektor: Göran Forsling
Examinator: Armen Asratian
Länk till kurshemsida på kursgivande institution
Ansvarig programnämnd: Data&Medie

Engelsk kursplan


Tekniska högskolan vid Linköpings universitet
Länk till sidans topp


Informationsansvarig: TFK , val@tfk.liu.se
Senast ändrad: 01/24/2013