Graph theory applications

Instructor
Rudiger Urbanke
Office INR 116
Phone +4121 6937692
Email [email protected]
Office Hours By appointment
Teaching Assistants
Lazlo Czap (for first 3 weeks)
Phone +4121 6937516
Office BC 048
Email [email protected]
Office Hours Office Hours TBD
Siddhartha Brahma
Phone +4121 6936654
Office INR032
Email [email protected]
Office Hours Office Hours TBD
Stanko Novakovic
Phone +4121 6937543
Office INN318
Email [email protected]
Office Hours Office Hours TBD
Student Assistant
Yannik Messerli
Email [email protected]
Lectures: Tuesday 11:15 – 13:00 Room: INM203
Thursday 16:15 – 18:00 Room: INM 201

Language: English Coefficient/Crédits: 4 ECTS

Link to the official course description. CourseInformation.pdf

Course Description

This class focuses on graph theory problems arising in Computer Science and Communications and discusses how to use methods and results from graph theory to solve them. The class will cover topics such as:

  1. Introduction to basic concepts in graph theory
  2. Job scheduling and graph coloring
  3. Network routing and graph connectivity
  4. Labyrinths and Eulerian paths
  5. Archeological data and trees
  6. VLSI design and planar graphs
  7. Internet routers and bipartite graphs
  8. Wireless Networks and geometric graphs

Grade

The grade will have four components – Homeworks (10%), Project (20%), Midterm Exam (30%) and Final Exam (40%)

Tentatively, there will be two homework sets on both sides of the Midterm exam. The precise topic of the project will be discussed in the class during the semester.

Textbook

We will be using the book Graph Theory with Applications by J.A. Bondy and U.S.R. Murty. You may find the electronic version of the book here

Special Announcements

For the Final Exam, just like the midterm, you are allowed to bring one A4 sheet with all the information you can write into it! Best of Luck!

Project

Please announce your group by April 25th. The due date of the project is Thursday May 30th.

Project Project.pdf

Detailed Schedule

Date Topic Assignment Due Date/Solutions Posted Remarks
19Feb Introduction; basic concepts, paths, cycles, special graphs, averaging principle
21Feb Exercise Session 1 Ex1.pdf
26Feb Eulerian graphs, Hamiltonian graphs
28Feb Exercise Session 2 Ex2.pdf
05Mar adjacency matrix A, powers of A, eigenvalues of A, incidence matrix B, rank of B
07Mar Exercise Session 3 Ex3.pdf
12Mar trees, cut edges, cut vertices, spanning trees, Cayley’s formula, the connector problem, Kruskal’s algorithm
14Mar Exercise Session 4 Ex4.pdf
19Mar proof of Kruskal’s algorithm; matchings and vertex covers; there will be only one hour of lecture and one hour of exercise session
Exercise Session 5 Ex5.pdf
21Mar Graded Homework 1 HW1.pdf
26Mar
28Mar
02Apr Easter break – no course
04Apr Easter break – no course
09Apr
11Apr Midterm Exam ( INJ 218); 4:15pm-6pm Midterm.pdf
16Apr Edge Colorings
18Apr Exercise Session 6 Ex6.pdf
23Apr Independent Sets and Ramsey Theory
25Apr Exercise Session 7 Ex7.pdf
30Apr Chromatic numbers
02May Exercise Session 8 Ex8.pdf
07May
09May Public holiday – no course
14May Graded Homework 2 Hw2.pdf
16May Network Flows, Max flow Min cut
21May Feasible Flows
23May Exercise Session 9 Ex9.pdf
28May
30May

Course Notes