FSF3700 Grafteori 7,5 hp

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.

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.

Grundläggande kunskaper motsvarande masterexamen i matematik. Minst en kurs om grafteori sedan tidigare.

"Graph Theory, (3rd edition)", by Reinhard Diestel, GTM Springer Verlag

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

• 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.

Godkända muntliga och skriftliga redovisningar

Svante Linusson

• 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.