Graph Theory and Algorithms

6 EC

Semester 1, period 1, 2

5122GRTO6Y

Owner Bachelor Wiskunde
Coordinator dr. V.S. Patel
Part of Exchange Programme Faculty of Science, specialisation BSc Mathematics, year 1Bachelor Wiskunde, year 3Dubbele bachelor Wis- en Natuurkunde, year 3

Course manual 2021/2022

Course content

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)(depending on time)
  • Extremal graph theory / Ramsey theory [Turan's theorem, Erdos-Stone theorem, Ramsey Theorem (depending on time)

Study materials

Literature

  • Doug West "Introduction to Graph Theory"

Syllabus

  • Lecture notes can be found on canvas.

     

    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.

     

    Further examples, explanations, exercises can be found in Doug West's book.

Other

  • Extra material can be found on canvas

Objectives

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

Teaching methods

    Learning activities

    Activiteit

    Aantal uur

    Lectures

    30

    Exercise classes

    28

    Mid-term exam

    0

    Final exam

    3

    Self-study

    104

    Attendance

    Programme's requirements concerning attendance (OER-B):

    • Each student is expected to actively participate in the course for which he/she is registered.
    • If a student can not be present due to personal circumstances with a compulsory part of the programme, he / she must report this as quickly as possible in writing to the relevant lecturer and study advisor.
    • It is not allowed to miss obligatory parts of the programme's component if there is no case of circumstances beyond one's control.
    • In case of participating qualitatively or quantitatively insufficiently, the examiner can expel a student from further participation in the programme's component or a part of that component. Conditions for sufficient participation are stated in advance in the course manual and on Canvas.
    • In the first and second year, a student should be present in at least 80% of the seminars and tutor groups. Moreover, participation to midterm tests and obligatory homework is required. If the student does not comply with these obligations, the student is expelled from the resit of this course. In case of personal circumstances, as described in OER-A Article A-6.4, an other arrangement will be proposed in consultation with the study advisor.

    Assessment

    Item and weight Details

    Final grade

    0.75 (75%)

    Final exam

    0.25 (25%)

    Homework assignments (best 5 out of 6)

    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 must score at least  50% on the exam  to pass the course.

    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.

     

    Inspection of assessed work

    Contact the course coordinator to make an appointment for inspection.

    Assignments

    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 will hand in solutions to 3 or 4 of the problems on each exercise sheet; some of these will be marked and returned to you. You may work in groups to solve the problems, but each student must write their own solutions for submission. You will find the homework assignments on canvas.

     

    Fraud and plagiarism

    The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

    Course structure

    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  

    Timetable

    The schedule for this course is published on DataNose.

    Honours information

    There is no honours extension for this course.

    Additional information

    Recommended prior knowledge: Basiswiskunde, Inleiding Grafentheorie.

    The course will be given in English.

    Contact information

    Coordinator

    • dr. V.S. Patel

    Staff

    • Mehmet Akif Yildiz (m.a.yildiz@uva.nl