Gráfok és algoritmusok
gyakorlat
2020. tavasz
Péntek, 10:15–11:45, IE219
A tárgy honlapja
Feladatsorok:
- Mohó algoritmusok, javítóutak
- Stabil párosítások, Gale–Shapley-algoritmus
- Stabil párosítások alkalmazásai
- Stabil párosítások nem csak páros gráfokban, Irwing-algoritmus
- Minimális vágások keresése, Nagamochi–Ibaraki-algoritmus
- Ritka tanúk, merevkörű gráfok
- Lamináris halmazrendszerek és Gomory–Hu-fák
- Teljes párosítások, Edmonds--algoritmus
- Lovász leemelési tétele
- Gyakorlás
- Minimális költségű folyamok, kerekítési lemma
- Baranyai-tétel
Vissza