**Program:**
1.Matchingi.
Matchingi (skojarzenia) oraz ich uogólnienia pojawiają się w bardzo wielu
kontekstach, bardziej i mniej oczywistych, m.in. przy:
* różnego typu przydziałach: zadań pracownikom lub maszynom, studentów szkołom itp.
* obliczaniu podgrafów, w których każdy wierzchołek ma mieć stopień z podanego przedziału. Za pomocą skojarzeń oblicza się np. pokrycia cyklowe (podgrafy, w kt. każdy wierzchołek ma mieć stopień 2) o najmniejszej/największej wadze. Takie pokrycia przydają się z kolei w znajdowaniu optymalnych dróg komiwojażera,
* aukcjach.
2.Matroidy.
Przykładami matroidów są lasy w grafach i podzbiory niezależnych liniowo
kolumn danej macierzy.
3.Rozlaczne sciezki, T-joins i T-cuts.
T-joiny mają zastosowania m.in. w wykrywaniu cykli o ujemnej wadze.
4.Przeplywy.
**Wymagania:** matematyka dyskretna, algorytmy i struktury danych
