Kursplan - Grafteori, nätverk och tillämpningar 7.5 hp

Graph Theory, Networks and applications

Kurskod: MAA600
Giltig från: HT14
Utbildningsnivå: Avancerad nivå
Ämnesgrupp: Matematik
Huvudområde(n): Matematik/Tillämpad matematik,
Successiv fördjupning: A1N (Avancerad nivå, har endast kurs/er på grundnivå som förkunskapskrav),
Akademi: UKK
Fastställandedatum: 2014-03-05

Syfte

Syftet med kursen är presentera de centrala begreppen och analysmetoderna inom grafteori, samt att i ett sammanhang av detta utveckla förmågan att hantera logik, algoritmer, modellering och beräkningar på ett givande sätt.
 

Lärandemål

Efter avklarad kurs ska studenten kunna

- korrekt redogöra för de grundläggande exemplen, idéerna och begreppen inom grafteori
- tillämpa grundläggande grafteoretiska satser
- algoritmer för att lösa vissa standardproblem inom grafteorin
- formulera allmänna matematiska problem i grafteoretiskt språk
- använda standardomformuleringar av grafteoretiska problem för att göra dem algoritmiskt lättare att lösa
- inom datavetenskap och informationsteknik tillämpa grafteoretiska begrepp och metoder

Innehåll

- Enkla grafer, multigrafer, pseudografer och digrafer
- Stigar, cykler, sammanhängande och avstånd
- Algoritmer för att beräkna kortaste avstånd i grafer
- Träd, bipartita grafer och andra elementära grafklasser
- Matchning
- Algoritm för att hitta matchningar i bipartita grafer
- Hörn- och kantfärgning
- Nätverk och flöden
- Representationer av grafer och algoritmiska aspekter

Undervisning

Föreläsningar och lektioner med arbete enskilt och i grupp.
 

Särskild behörighet

120 hp inom teknik, naturvetenskap eller ekonomi varav minst 60 hp inom teknik och naturvetenskap inklusive 30 hp matematik/tillämpad matematik vari ingår Vektoralgebra, grundkurs, 7,5 hp eller motsvarande samt antingen Sannolikhetslära, 7,5 hp eller motsvarande eller Diskret matematik, 7,5 hp eller motsvarande. Dessutom krävs Svenska B/Svenska 3 samt Engelska A/Engelska 6. I de fall kursen ges på engelska görs undantag från kravet på Svenska B/Svenska 3.

Examination

Tentamen (TEN2), 4 högskolepoäng, betyg 3, 4 eller 5
Projekt (PRO1), 3,5 högskolepoäng, betyg 3, 4 eller 5
 

En student som har ett intyg från MDH avseende sin funktionsnedsättning har möjlighet att anmäla önskemål om anpassning vid salstentamina eller annan examinationsform i enlighet med Regler och anvisningar för examination på grundnivå och avancerad nivå vid Mälardalens högskola (2016/0601). Det är examinator som, utifrån det intyg som utfärdats, beslutar om eventuell anpassning och i så fall vilken anpassning som ska gälla.

Misstankar om vilseledande vid examination (fusk) anmäls, enligt högskoleförordningen, till högskolans rektor och prövas av högskolans disciplinnämnd. Om disciplinnämnden anser att en student gjort sig skyldig till en disciplinförseelse fattar nämnden beslut om en disciplinär åtgärd, vilket är varning eller avstängning.

Regler och anvisningar för examination

Betyg

Ges något av betygen 5, 4, 3

Miljöaspekter

Miljöaspekter har beaktats men uppmärksammas inte i kursens lärandemål.
 

Kurslitteraturen är preliminär till 3 veckor innan kursstart. Kurslitteratur kan vara giltigt över flera terminer.

Giltig från: HT14

Beslutsdatum: 2014-08-08

Senaste uppdatering: 2014-08-25

Böcker

West, Douglas Brent;

Introduction to graph theory

ISBN: 0-13-014400-2 LIBRIS-ID: 4548461

xix, 588 s.

Giltig från: HT15

Beslutsdatum: 2015-06-23

Senaste uppdatering: 2015-06-23

Böcker

Wilson, Robin J.;

Introduction to graph theory

ISBN: 9780273728894 (pbk.) LIBRIS-ID: 11887022

viii, 184 s.