Uni-Logo
You are here: Home Lehre Aktuelle Lehre Lecture Graph Theory (Summer 2022)
Document Actions

Lecture Graph Theory (Summer 2022)

News

  • 09.08.2022 10:30 (051-002-007): Early exam - Please notify us if you want to participate
  • 24.04.2022 ILIAS online

Contents

This lecture deals with graph theory for undergraduate computer science students. Among other things, the following topics are taught:

  1. DAGs
  2. Topological Sorting
  3. Connectivity
  4. Dominators
  5. Geometric Graphs
  6. BFS/DFS
  7. Min-Flow-Max-Cut Theorem
  8. Weighted Matching in Bipartite Graphs
  9. Colering, Cliques
  10. Planar Graphs

Schedule

  • Lecture Tuesday (2h): 16:15-18:00 101-00-026 
  • or Tuesday (1h): 16:15-17:00 101-00-026  on exercise days
  • Zoom:  Meeting-ID: 614 7417 3428 Passcode: Graph2022
Date Lecture Exercise  
26.04.2022 01: Organization & Undirected Graphs (2h) -  
03.05.2022 02: Basic Properties of Undirected Graphs (2h) -  
10.05.2022 03: Directed Graphs (1h) 01  
17.05.2022 04: DFS, Dominators  (2h) -  
24.05.2022 05: Paths and Connectivity (1h) 02  
31.05.2022 06: BFS  (2h) -  
14.06.2022 07: Topological Sorting (1h) 03  
21.06.2022 08: Min Flow Max Cut  (2h) -  
28.06.2022 09: Weighted Matching in Bipartite Graphs (1h) 04  
05.07.2022 10: Geometric Graphs  (2h) -  
12.07.2022 11: Planarity (1h) 05  
19.07.2022 12: Random Graphs  (2h) -  
26.07.2022 13: Probabilistic Method (1h) 06  

Material

  • Lecture slides can be found before the lecture on  ILIAS 
  • Annotated slides will be published on  ILIAS  as welll.
  • Exercise sheets will be published on Tuesday on  ILIAS
  • Lecture Recording will be made available asap on  ILIAS 

Exercise Classes

  • Group 1, Iroda Ulmasboeva, 17-18, 051-00-006
  • Group 2, Marco Kaiser, 17-18, Zoom 
  • Group 3, Sneha Mohanty, 17-18, 101-03-026
  • Group 4, Iroda Ulmasboeva, 18-19, 101-00-006
  • Group 5, Marco Kaiser, 18-19, Zoom
  • Group 6, Sneha Mohanty, 18-19, 101-016/018

We will reassign the groups in the first two weeks depending on your online/on-site and language preferences. Instructions will appear here.

Exam

The first exam takes place on 23.09.2022 at 09:00 (am) in 101-00-026 (for students with last names starting with letters A-H) and 101-00-036 (for students with last names starting with letters J-Z). It is a closed book exam lasting 90 minutes. Please have your student ID ready.

No aids are allowed other than writing materials. You can bring beverages and food, but no extra paper.  You can register for the exam online using the online system. In case you are not sure whether your registration has worked, you can write the exam and we will work out your eligibility later on.

In case you feel symptoms of COVID, please do not come. In case you are ill or you suspect you have COVID-19 you can write the exam in 6 months. There is only a voluntary mask requirement in place at this moment.

Literature

  • Introducation to Graph Theory, Second Edistion, Douglas West, Prentice Hall 2002.
  • Graphentheoretische Konzepte und Algorithmen, Sven Oliver Krumke und Hartmut Noltemeier. Springer 2012. (Online)
  • Graph Theory, Reinhard Diestel, Electronic Edition 2010 pdf

 

Further bibliographical references will be published during the event.

 

 

Personal tools