Graph Theory and Algorithms

Studiewijzer 2017/2018

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)

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

Definitions from the course:

connected graph, forest, acyclic graph, tree, leaf, spanning subgraph, graph distance

matching, saturated vertex, perfect matching, maximum/maximal matching, alternating/augmenting path, vertex cover, independent set, edge cover

separating set, vertex connectivity, separating set of edges, edge connectivity, edge cut, block, block-cutpoint graph, internally
vertex disjoint paths, ear, ear decomposition A,B-paths

proper k-colouring, chromatic number, clique number, girth, random graph, chromatic polynomial

subdivision of a graph

Algorithms from the course:

-Kruskal's algorithm
-Dijkstra's algorithm
-bipartite maximum matching algorithm
-Hungarian algorithm
-Greedy colouring algorithm

Theorems from the course:

- three equivalent characterisations of trees
- exchange property of trees
- proof of correctness of Kruskal's algorithm
- proof of correctness of Dijkstra's algorithm

-characterisation of maximum matchings in terms of augmenting paths
-Hall's Theorem
-König-Egerváry Theorem
-Gallai's Theorem
-König's Theorem

-Whitney's inequality
-Properties of blocks and the block-cutpoint graph
-Whitney's Theorem (Menger's Theorem for 2-connected graphs)\
-Whitney's Theorem (Characterisation of 2-connectedness in terms of ear
decompositions)
-Menger's Theorem

-Basic bounds for chromatic number
-Brooks Theorem
-Mycielski's construction
-Existence of graphs with high girth and chromatic number
(probabilistic proof)
-chromatic polynomial is a polynomial and the deletion contraction
recursion

-Kuratowski's Theorem

Onderwijsvormen

• Hoorcollege
• Werkcollege

Verdeling leeractiviteiten

Aanwezigheid

Aanwezigheidseisen opleiding (OER-B):

• Van elke student wordt actieve deelname verwacht aan het onderdeel waarvoor hij/zij staat ingeschreven.
• Als een student door overmacht niet aanwezig kan zijn bij een verplicht onderdeel van het onderdeel, dient hij/zij dit zo snel mogelijk schriftelijk te melden bij de betreffende docent. De docent kan dan, eventueel na overleg met de studieadviseur, besluiten om de student een vervangende opdracht op te leggen.
• 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.
• 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.

Aanvullende eisen voor dit vak:

Presence at classes is compulsory. If you are absent from more than 20% of classes, you will lose your right to take the retake exam as stated in OER-B article 4.9 paragraph 2.

Toetsing

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.

Opdrachten

There will be 6 homework assignments each consisting of around 6-8 problems. You must hand in solutions to all problems and two or three of them will be marked. 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: www.uva.nl/plagiaat

Weekplanning

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