Grafteori

5 hp

Kursplan, Grundnivå, 1MA170

Kod
1MA170
Utbildningsnivå
Grundnivå
Huvudområde(n) med fördjupning
Matematik G1F
Betygsskala
Med beröm godkänd, icke utan beröm godkänd, godkänd, underkänd
Fastställd av
Teknisk-naturvetenskapliga fakultetsnämnden, 22 februari 2022
Ansvarig institution
Matematiska institutionen

Behörighetskrav

30 hp matematik. Linjär algebra II genomgången. Sannolikhet och statistik eller Sannolikhetsteori I genomgången.

Mål

Efter godkänd kurs ska studenten kunna:

  • formulera och bevisa centrala satser om träd, matchningar, konnektivitet, färgläggningar och planära grafer;
  • beskriva och tillämpa några grundläggande algoritmer för grafer;
  • använda grafteorin som verktyg vid modellering.
  • redogöra för viktiga klasser av grafteoretiska problem;

Innehåll

Grundläggande grafteoretiska begrepp: vägar och cykler, konnektivitet, träd, uppspännande delgrafer, bipartita grafer, Hamilton- och Eulercykler. Algoritmer för kortaste väg och uppspännande träd. Matchning. Planära grafer. Färgläggning. Flöden i nätverk, maxflöde-minsnittsatsen. Erdös-Rényi slumpgrafer. Szemerédis regularitetslemma. Oändliga grafer. Tillämpningar i datavetenskap. Extremal grafteori.

Undervisning

Föreläsningar, lektioner och räkneövningar.

Examination

Skriftligt prov vid kursens slut (2 hp). Inlämningsuppgifter (3 hp).

Om särskilda skäl finns får examinator göra undantag från det angivna examinationssättet och medge att en enskild student examineras på annat sätt. Särskilda skäl kan t.ex. vara besked om särskilt pedagogiskt stöd från universitetets samordnare för studenter med funktionsnedsättning.

FÖLJ UPPSALA UNIVERSITET PÅ

facebook
instagram
twitter
youtube
linkedin