Vær opmærksom på at dette website indeholder et arkiv med historiske data. Det aktuelle kursuskatalog findes på kursuskatalog.au.dk

AU kursuskatalog arkiv

[Forside] [Hovedområder] [Perioder] [Udannelser] [Alle kurser på en side]

Grafteori 2 (Q1+Q2) ( efterår 2010 - 10 ECTS )

Rammer for udbud

  • Uddannelsessprog: engelsk (eller dansk)
  • Niveau: Kandidatkursus.  
  • Semester/kvarter: 1. + 2. kvarter (efterår 2010).
  • Timer per uge: 3 hver uge + 2 hver anden uge.  
  • Deltagerbegrænsning:
  • Undervisningssted: Århus
  • Hovedområde: Det Naturvidenskabelige Fakultet
  • Udbud ID: 26032

Formål

Efter endt kursus vil studenten kunne arbejde med matchinger i grafer, farvninger af kanter og knuder i grafer, samt udvalgte grafteoretiske algoritmer. Listen af behandlede algoritmer omfatter korteste stier, perfekt matching, optimal assignment, det kinesiske postbuds problem oga maksimalt flow i en orienteret graf. Der åbnes mulighed for, at studenterne kan ønske gennemgang af yderligere algoritmer eller problemstillinger knyttet til konstruktion af algoritmer.

Indhold

Kurset vil omfatte emnerne konnektivitet og matching (kap. 8), farvning af knuder og kanter i en graf (kap. 9), introduktion til matroider (kap.10) og flows i netværk (kap. 12) i bogen af Tulasiraman og Swamy.
Matching vil blive relateret til heltalsprogrammering. 

Faglige forudsætninger

Grafteori 1, lineær programmering, mens heltalsprogrammering vil være en fordel.

Underviser

Steen Friis Møller.

 

Undervisnings- og arbejdsform

3 timer pr. uge og mindst 6 øvelsesgange à 2 timer.

.

 

Litteratur

K. Tulasiraman og N.S. Swamy: Graphs: Theory and Algorithms , John Wiley & Sons, INC.

L.A. Wolsey and G.L. Nemhauser: Integer and combinatorial optimization , Wiley & Sons, INC., 1999.

Udbyder

Institut for Matematiske Fag.

 

Tilmelding til undervisning

På selvbetjening https://mit.au.dk fra den 1. til den 15. maj.

Eftertilmeldinger: Kontakt Oddbjørg Wethelund, oddbjorg@imf.au.dk

 

Læringsmål

Efter endt kursus vil den studerende være fortrolig med

  • begreberne matchings, farvning af både knuder og kanter, optimale flows i netværk, assign problemer i grafer samt robusthed over for enkelt-fejl i såvel knuder somkanter.
  • Den teoretiske behandling af emner vil blive forklaret således at udvalgte problemstillinger hos virksomheder kan genkendes som foran nævnte generelle problemstillinger.
  • Den studerende vil tillige være i stand til at gennemføre de matematiske ræsonnementer, der gør de gennemgåede algoritmer gyldige.

Bedømmelse

  • Mundtl. eks., bedømt efter 7-skala med ekstern censur
    • 5 xxxxx

30 min. mundtlig eksamen uden forberedelse.