Kursplan - Grafteori, nätverk och tillämpningar

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

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, samt Diskret matematik, 7,5 hp, eller motsvarande. Dessutom krävs Svenska 3 eller Svenska nivå 3 samt Engelska 6 eller Engelska nivå 2. I de fall kursen ges på engelska görs undantag från kravet på Svenska 3 eller Svenska nivå 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 besked om riktat pedagogiskt stöd från MDU kan ansöka om anpassning vid examinationen. Det är examinatorn som beslutar om eventuell anpassning utifrån beskedet och förutsättningarna i övrigt.

Misstankar om vilseledande vid examination (fusk) anmäls, enligt högskole-förordningen, till rektor och prövas av universitetets 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 för viss tid.

Betyg

Ges något av betygen 5, 4, 3