Discrete part. Literature: lecture notes and Cook, Cunningham, Pulleyblank, Schrijver, Combinatorial Optimisation, Wiley 1998.
Tutorials: It is necessary to pass both discrete and continuous part of the tutorial. For the discrete part, in order to pass you need one of the following: a. pass a test or b. make a team presentation of an interesting topic related to the lecture or c. make a team presentation of computer experiments related to topics of the lecture. I need to approve the teams and topics for b., c.
February 17: introduction, repetition of basic notions of the graph theory, euler tour, cycle space of a graph, Hamiltoniam cycles, Sperner trees, min spanning tree, planar graphs and their geometric duals.
February 24: matroids: basic definitions, rank function, submodularity and its significance for modelling utility
February 24 tutorial: basic notions of matroids, prove that vectorial and graphic "matroids" are indeed matroids. Prove that U(2,4) is not representable over F2.
March 3: matroids: greedy algorithm, dual matroid, grapic matroid, independent and dependent set of a matroid
March 3 tutorial: Let G be an embedded planar graph. Proof that the dual of its graphic matroid is isomorphic to the graphic matroid of its geometric dual.
March 10: matching in graphs, Tutte-Berge Theorem, Edmonds algorithm
March 17a: matchings and edge-cuts in planar graphs, Ising partition function
March 17b: Chinese postman problem and Travelling salesman problem