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

Lecture Graph Theory (Summer 2022)

News

  • 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, Hamiltonian Path & Cycles
  10. Erdös-Renyi-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

There will be a written exam lasting 90 minutes. You can register for the exam online using the online system. No aids are allowed other than writing materials.

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