8. Synopsis
Network flows, Ford-Fulkerson algorithm, integrality lemma, generalizations of the flow problem.

Characterization of bipartite graphs, maximum matching in bipartite graphs. Theorems of Kőnig, Frobenius and Hall.

Graph colourings. Lower and upper bounds on the chromatic number. Edge colouring of graphs, Vizing's theorem. Edge colouring of bipartite graphs using the integrality lemma.

Egerváry's algorithm for finding maximum total weight matching and perfect matching in bipartite graphs.

Systems of linear inequalities, basic linear programming, solving bivariate problems by graphical method. Solving linear inequality systems by Fourier-Motzkin elimination. Necessary and sufficient conditions for solving systems of linear equations with non-negative variables and systems of linear inequalities: Farkas' lemma.

The basic problem of linear programming in matrix form. Necessary and sufficient conditions for the boundedness of the objective function of a linear program. Concept of duality of a linear program, dualities of linear programs written in different forms.

Duality theorem of linear programming. Algorithmic complexity of the linear programming problem. The basic task of integer programming, its complexity. Formalization of optimization problems as integer programming problems.

Integer programming with a totally
unimodular coefficient matrix. Applications in the area of bipartite
matchings and network flow problems: maximum flow, minimum cost flow,
and multicommodity flow problems.

The notions of local edge and vertex
connectivity and global edge and vertex connectivity, the corresponding
Menger theorems (iteration). Max-return order, Nagamochi-Ibaraki's
algorithm for determining edge connectivity.

Algorithm for increasing graphs to be 2-edge-connected, lower bound on the number of edges required. Algorithm for finding minimum cost spanning tree. Ear resolution, directing graphs to ensure strong connectivity.

Approximation algorithms. Edge chromatic number, approximation of planar graph chromatic number with additive error, approximation of longest cycle with additive error. 2-approximation for the size of covering vertex set, logarithmic approximation for set covering problem.

Scheduling problems. Basic concepts, notation, useful methods: SPT ordering and list scheduling. FD and FFD heuristics for the crate packing problem.

Recap, summary, systematic review of the material studied. Description of the current test items for the oral examination and detailed expectations for each item.

10. Assessment
During the semester:

There will be two midterms. Both will consist of 4-4 exercises, with a total score of 50 points per test. Both must be at least 20 points to obtain a signature.

Exam period:

You can apply for the exam if you have a valid signature. If a signature is obtained, the student is offered a mark based on the total number of marks obtained in the final examination, as follows: from 40 points satisfactory, from 55 to medium, from 70 to good and from 85 to excellent. The lecturer must be informed of the acceptance of the grade offered during the make-up week. Those who accept the grade offered will not be allowed to sit the oral examination. Anyone who does not notify the lecturer of the acceptance of the mark may obtain the mark in the oral examination. In the oral examination, you may improve the grade offered by up to one mark, and you may lower it without limit.