**Program:**
1.Matchingi.
Matchingi (skojarzenia) oraz ich uogolnienia pojawiają się w bardzo wielu
kontekstach, bardziej i mniej oczywistych, m.in. przy:
* rożnego typu przydziałach: zadań pracownikom lub maszynom, studentow szkołom itp.
* obliczaniu podgrafow, w ktorych 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 drog komiwojażera,
* aukcjach.
2.Matroidy.
Przykładami matroidow 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
