2WO12: Optimalisering in Netwerken
Winter/Spring 2012

General information:

The course takes place in Semester B, Kwartiel 3, on tuesday, wednesday, and friday.
The college on tuesday 3+4 is in potentiaal 13.03
The college on wednesday 1+2 is in potentiaal 10.05
The instructie on friday 5+6 is in potentiaal 10.05 (exception: thursday 5+6, April 5)

Attention! First lecture: Wednesday, February 8

Hand-outs:
1. The first three lectures are covered by `Grafen: kleuren en routeren' (GKR). Here is the ps-file.
2. Here is the ps-file `Graafrepresentaties en complexiteit' (GR&C) for the fourth lecture.
3. Here is the ps-file `A course in combinatorial optimization' (CO) for lectures 5-7.
    (This is a shortened version of a booklet by Lex Schrijver; the long version is here.)
4. Here is the ps-file `NP-completeness' (NP) for lecture 8.

Slides:
Lecture 1: slides
Lecture 2: edge-coloring and vertex-coloring
Lecture 3: slides
Lecture 4: slides and slides
Lecture 5: slides and slides
Lecture 6: slides
Lecture 7: slides
Lecture 8: slides and slides

Old exams: 2009; 2010; 2011

Summary of lectures:

• Lecture 1: Introduction: Mainly chapter 1 of GKR.
  Introductory definitions; handshake lemma; De Bruijn sequences;
  Eulerian graphs; Hamiltonian graphs;
  Extra: web-page with a graph theory puzzle

  The following exercises (in GKR) are recommended; please prepare them for the instructions.
  Starred exercises (*) contain crucial material for the course.
  5, 15, 16*,18, 23*, 25*, 26, 28*, 29, 32, 34, 35, 43*, 44, 45, 47,48*, 50,51, 52 54, 57, 59* t/m 62*, 64, 65, 67*, 69, 74*, 75*, 76, 77*, 79*, 80*, 83, 84*, 87, 88 t/m 91, 92, 95, 103 t/m 105.

• Lecture 2: Coloring problems: Chapter 2 of GKR.
  Edge-colorings of graphs: Theorem of Kőnig for bipartite graphs; Vizing's theorem.
  Vertex-colorings of graphs: clique number; clique number versus chromatic number;
  planarity; Euler's formula; 4-color theorem; 5-color theorem.
  Extra: web-page with a planarity game

  Recommended exercises (from GKR):
  Edge-coloring: 40, 41, 42, 43*, 44, 46 t/m 48, 49*, 50*, 52, 53.
  Vertex-coloring: 2, 3, 4, 5, 6, 7, 9*, 10
  Bipartite graphs: 37, 38*, 39*
  Planar graphs: 15, 16, 17, 24*, 25*, 26, 27*, 28*, 29*, 30*, 31*

• Lecture 3: Max-flows and min-cuts: Chapter 3 of GKR.
  The Max-flow-Min-Cut theorem, and the algorithm of Ford and Fulkerson.
  Extra: pdf-file with Lex Schrijver's article on the history of the transportation and the maximum flow problem.

  Recommended exercises (from GKR):
  3, 4, 5*, 6, 7, 8, 9*, 10, 11*, 12, 13, 14, 15, 16*, 17*, 18.

• Lecture 4: Algorithms and complexity: Handout GR&C.
  Formal definitions of algorithmic problems, input, time complexity, etc.
  Big-O-notation; polynomial versus exponential time;
  graph traversal; BFS and DFS; cut-vertices;

  Recommended exercises (from GR&C):
  1,3,4,9,10,11,12.

• Lecture 5: Shortest paths: Sections 1.1-1.3 of CO.
  Dijkstra; Bellman-Ford;
  topological sorting.

  Recommended exercises (from CO): 1.1 thru 1.6
  Recommended exercises (extra sheet): 1,2,3,4,5

• Lecture 6: Spanning trees: Section 1.4 of CO.
  Prim-Dijkstra algorithm; Kruskal algorithm.
  Pruefer codes; Theorem of Cayley.

  Recommended exercises (from CO): 1.7 thru 1.9
  Recommended exercises (extra sheet): 2,3,4,5,6,7,8

• Lecture 7: Bipartite matchings: Sections 3.1-3.4 of CO.
  unweighted and weighted bipartite matching.
  Theorem of Kőnig

  Recommended exercises (from CO): 3.2 thru 3.25
  Recommended exercises (extra sheet): 1,2,3

• Lecture 8: Complexity theory: NP and Sections 6.1-6.10 of CO.
  Turing machines; non-determinism; P and NP; reductions; NP-completeness; SAT
  NP-completeness of: Co-Clique, 0-1-IP, 3SAT, PARTITION, Hamiltonian Cycle, Vertex-coloring, Edge-coloring

  Recommended exercises (from NP): 1-5
  1-5 in opg-np2 (Solutions here)