Lecture Graph Theory (Summer 2022)
News
- 10.10.2022 10 am, inspection of the exam (051-002-007)
Contents
This lecture deals with graph theory for undergraduate computer science students. Among other things, the following topics are taught:
- DAGs
- Topological Sorting
- Connectivity
- Dominators
- Geometric Graphs
- BFS/DFS
- Min-Flow-Max-Cut Theorem
- Weighted Matching in Bipartite Graphs
- Colering, Cliques
- 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.