Graph Theory and Algorithms

6 EC

Semester 1, periode 1, 2

5122GRTO6Y

Eigenaar Bachelor Wiskunde
Coördinator dr. V.S. Patel
Onderdeel van Bachelor Wiskunde, jaar 3

Studiewijzer 2019/2020

Globale inhoud

This following topics will be covered in the course:

  • Trees - properties of trees, exchange property, Kruskal's algorithm, Dijkstra's algorithm
  • Matchings - augmenting paths, Hall’s Theorem, König-Egerváry Theorem, duality between independent sets and edge covers, Hungarian algorithm 
  • Connectivity - blocks, ear decompositions, Menger's Theorem
  • Graph Colouring - basic bounds for chromatic number, Brooks' Theorem, existence of graphs with high girth and chromatic number, chromatic polynomial 
  • Planar graphs - Recap of results from previous course, characterising planar graphs (Kuratowski’s Theorem)
  • Extremal graph theory / Ramsey theory

Studiemateriaal

Literatuur

  • Doug West "Introduction to Graph Theory"

Syllabus

  • Lecture notes can be found on my website: https://sites.google.com/site/vireshspatel/teaching-1

     

    The notes will contain all definitions, theorems and proofs, but no examples. Examples will be given during lectures so it is recommended that you take notes during lectures to supplement the printed notes.

Overig

  • Extra material can be found on my website: https://sites.google.com/site/vireshspatel/teaching-1

Leerdoelen

  • The student should be able to reproduce definitions and statements of theorems from the course;
  • The student should be able to reproduce proofs from the course by summarising and remembering the main ideas/steps;
  • The student should be able to check if definitions have been satisfied, to give examples and non-examples of objects satisfying the definition, and to derive simple consequences from definitions;
  • The student should be able to apply results from the course to solve unfamiliar problems in graph theory;
  • The student should be able to generalise proofs in simple ways and be able to analyse where in a proof certain assumptions have been used;
  • The student should be able to apply mathematical/combinatorial proof techniques such as proofs by induction, proofs by contradiction, use of the extremal principle, to problems in graph theory;
  • The student should be able to apply algorithms from the course to given instances of relevant optimisation problems;
  • The student should be able to write clear mathematics proofs and explain their ideas in a clear way.

Onderwijsvormen

  • Hoorcollege
  • Werkcollege

Verdeling leeractiviteiten

Activiteit

Aantal uur

Lectures

30

Exercise classes

28

Mid-term exam

0

Final exam

3

Self-study

104

Aanwezigheid

Aanwezigheidseisen opleiding (OER-B):

  • Van elke student wordt actieve deelname verwacht aan het onderdeel waarvoor hij/zij staat ingeschreven.
  • Als een student door persoonlijke omstandigheden niet aanwezig kan zijn bij een verplicht onderdeel van het programma, dient hij/zij dit zo snel mogelijk schriftelijk te melden bij de betreffende docent en de studieadviseur.
  • Het is niet toegestaan om verplichte onderdelen van een onderdeel te missen als er geen sprake is van overmacht.
  • Bij kwalitatief of kwantitatief onvoldoende deelname, kan de examinator de student uitsluiten van verdere deelname aan het onderdeel of een gedeelte daarvan. Voorwaarden voor voldoende deelname worden van te voren vastgelegd in de studiewijzer en op Canvas.
  • Bij alle onderwijseenheden van jaar 1 en 2 is een student verplicht bij minimaal 80% van de werkcolleges en tutoraten aanwezig te zijn. Bovendien moet worden deelgenomen aan eventuele tussentoetsen en verplicht gesteld huiswerk. Als niet aan deze verplichting is voldaan, wordt de student uitgesloten voor de herkansing van de onderwijseenheid. In geval van persoonlijke omstandigheden, zoals in OER-A Artikel 6.4 omschreven, wordt in overleg met de studieadviseur een afwijkende regeling voorgesteld.

Toetsing

Onderdeel en weging Details

Eindcijfer

0.75 (75%)

Final Exam

0.25 (25%)

Homework

Continuous assessment (i.e. homework) counts 25% towards your final grade. There will be 6 exercise sheets and your best 5 marks will count towards the 25%. Combinatorial problem solving is an important part of this course and is assessed mainly through the homework. The remaining 75% is assessed via the final exam. There is no midterm exam.

You may only take the resit exam if you score at least half marks on the continuous assessment.  If you take the resit exam, the continuous assessment only counts 25% towards your mark if it increases your grade; otherwise the resit exam counts 100% towards your final grade.

 

Opdrachten

There will be 6 homework assignments each consisting of around 6 problems. These will be graded and your best 5 out of 6 marks will count  25% towards your final grade. You must hand in solutions to all problems; some of these will be marked and returned to you. You will find the homework assignments on the course webpage.

 

Fraude en plagiaat

Dit vak hanteert de algemene 'Fraude- en plagiaatregeling' van de UvA. Hier wordt nauwkeurig op gecontroleerd. Bij verdenking van fraude of plagiaat wordt de examencommissie van de opleiding ingeschakeld. Zie de Fraude- en plagiaatregeling van de UvA: http://student.uva.nl

Weekplanning

Weeknummer Onderwerpen Studiestof
1 Recap on the basic notation and terminology. Begin the section on trees proving three equivalent characterisations of trees.   
2 Other characterisation of trees. Exchange property for trees. Description of Kruskal's algorithm. Proof of correctness of Kruskal's algorithm.  
3 Description of Dijkstra's algorithm. Proof of correctness of Dijkstra's algorithm.  
4 Begin topic on matchings. Several definitions. Characterise maximum matchings in terms of augmenting paths. Statement and proof of Hall's Theorem.  
5 State and prove various results relating the sizes of maximum independent sets / matchings and minimum vertex / edge covers in (bipartite) graphs. In particular, prove the Konig-Egervary Theorem, Gallai's Theorem, and Konig's Theorem.  
6 Description and proof of correctness of maximum matching algorithm in bipartite graphs. Description of the Hungarian algorithm for finding maximum weight perfect matchings in weighted bipartite graphs.   
7 Proof of correctness for the Hungarian Algorithm. Relationship between the various algorithmic problems  studied and the famous P vs NP problem. Begin section of graph connectivity, defining the various notions of connectivity and how they relate to each other.  
8 Define the notion of blocks and prove various properties of blocks. Understand the structure of connected graphs in terms of blocks by showing that the block-cutpoint graph is a tree.  
9 Understand the structure of 2-connected graphs. State and prove Menger's Theorem for the case of 2-connected graphs and characterise 2-connected graphs in terms of ear decompositions. Begin proof of Menger's Theorem in full generality.  
10 Finish poof of Menger's Theorem. Recall various definitions and results related to graph colouring including the greedy colouring algorithm. Describe intelligent greedy colouring, i.e. the Szekeres-Wilf Theorem. State Brooks' Theorem.  
11 Prove Brooks' Theorem. Describe Mycielski's construction for triangle-free graphs with large chromatic number.  
12 Use the probabilistic method to show the existence of graphs with large girth and chromatic number. Define the chromatic polynomial and show it is a polynomial. State and prove the deletion-contraction recursion for the chromatic polynomial.   
13 Recap on planar graphs. State Kuratowski's Theorem. Proved the easy direction and half of the hard direction.  
14 Finish the proof of Kuratowski's Theorem.  
15 Revision  
16 Revision  

Rooster

Het rooster van dit vak is in te zien op DataNose.

Honoursinformatie

There is no honours extension for this course.

Aanvullende informatie

Recommended prior knowledge: Basiswiskunde, Inleiding Grafentheorie.

The course will be given in English.

Contactinformatie

Coördinator

  • dr. V.S. Patel