Kursen behandlar: Teorin för matchningar. Strukturatser om 2- och 3-sammanhängandekomponenter hos en graf, även Maders och Mengers satser. Teori om minorer, planeritet. Färgning av flera olika slag. Perfekta grafer. Hadwigers förmodan. Slumgrafer och slumpnätverk. Den probababilistiska metoden. Szemeredis regularitets lemma, extremala grafer, fast mixing, olika algebraiska tekniker.
FSF3700 Grafteori 7,5 hp
Denna kurs är avvecklad.
Sista planerade examination: HT 2022
Avvecklingsbeslut:
Ingen information tillagdInformation per kursomgång
Kursomgångar saknas för aktuella eller kommande terminer.
Kursplan som PDF
Notera: all information från kursplanen visas i tillgängligt format på denna sida.
Kursplan FSF3700 (VT 2019–)Innehåll och lärandemål
Kursinnehåll
Lärandemål
Kursen syftar till att ge förtrogenhet med mer avancerad teori och metoder inom grafteori. Målsättningen är att ge fördjupade kunskaper vilka utgör en lämplig grund såväl för forskning i matematik som för tillämpningar inom närliggande discipliner. Konkret ska studenten efter genomgången kurs
- Behärska en stor mängd grafteoretiska begrepp och termer.
- Förtrogenhet med att formulera problem i grafteoretiska termer.
- Ökad färdighet i problemlösning inom grafteori.
- Förstå sammanhängande grad och kant-sammanhängande av graf. Kunna struktursatser och kunna redogöra för och använda Maders och Mengers satser.
- Förstå och kunna använda begreppet minor av en graf. Känna till många olika sortser färgningsproblem för grafer. Ökad förmåga att formulera tillämpade problem som färgningsproblem.
- Kunna förstå och använda olika modeler för slumpgrafer (slumpnätverk).
- Kunna göra tillämpningar av den probabilistiska metoden inom grafteori.
- Kunna använda Szemerdis Regulatitetslemma och ha en grundläggande idé om ett bevis.
- Känna till kunna använda algebraiska tekniker för att studera grafer och problem på grafer.
Kurslitteratur och förberedelser
Särskild behörighet
Grundläggande kunskaper motsvarande masterexamen i matematik. Minst en kurs om grafteori sedan tidigare.
Rekommenderade förkunskaper
Utrustning
Kurslitteratur
"Graph Theory, (3rd edition)", by Reinhard Diestel, GTM Springer Verlag
Examination och slutförande
När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.
Betygsskala
Examination
- INL1 - Inlämningsuppgift, 7,5 hp, betygsskala: P, F
Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.
Examinator får medge annan examinationsform vid omexamination av enstaka studenter.
Muntliga och skriftliga redovisningar.
Övriga krav för slutbetyg
Godkända muntliga och skriftliga redovisningar
Möjlighet till komplettering
Möjlighet till plussning
Examinator
Etiskt förhållningssätt
- Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
- Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
- Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.