1. hét |
február 10. |
Gráfelméleti alapfogalmak, 1. rész (1. fejezet): részgráf, komplementer (1.1. fejezet), gráfok izomorfiája (1.2. fejezet), irányított gráfok (1.5. fejezet) |
február 11. |
1. gyakorlat |
2. hét |
február 17. |
Gráfelméleti alapfogalmak, 2. rész (1. fejezet): összefüggőség, komponens (1.3. fejezet), fa, feszítőfa (1.4. fejezet) |
február 18. |
2. gyakorlat |
3. hét |
február 24. |
Euler-séták és Euler-körséták (4. fejezet), Hamilton-utak és Hamilton-körök (5. fejezet) |
február 25. |
3. gyakorlat |
4. hét |
március 3. |
Szélességi keresés (2. fejezet, algoritmus vetítés), minimális összsúlyú feszítőfa (3. fejezet) |
március 4. |
4. gyakorlat |
5. hét |
március 10. |
Gráfok színezése, 1. rész (6. fejezet): páros gráfok (6.1. fejezet), mohó színezés (6.2. fejezet), klikkszám és kromatikus szám (6.3. fejezet) |
március 11. |
5. gyakorlat |
6. hét |
március 17. |
Gráfok színezése, 2. rész (6. fejezet): Zykov-konstrukció (6.14. tétel), intervallumgráfok (6.4. fejezet); Párosítások (7. fejezet) |
március 18. |
6. gyakorlat |
7. hét |
március 24. |
Független ponthalmaz és lefogó élhalmaz (7.1. fejezet) |
március 25. |
7. gyakorlat |
8. hét |
március 31. |
Párosítások páros gráfban, 1. rész (7.2. fejezet): javítóutas algoritmus (algoritmus vetítés), Kőnig-tétel (7.18. következmény) |
április 1. |
8. gyakorlat |
9. hét |
április 7. |
Párosítások páros gráfban, 2. rész (7.2. fejezet): Hall-tétel (7.22. tétel), Frobenius-tétel (7.24. következmény), teljes párosítás létezése reguláris páros gráfban (7.25. következmény); Gráfok élszínezése (8. fejezet) |
április 8. |
9. gyakorlat |
10. hét |
április 14. |
A maximális folyam feladat, 1. rész (9. fejezet): a javítóutas algoritmus maximális folyam keresésére (9.1. fejezet) |
április 15. |
10. gyakorlat |
– |
április 17–27. |
Tavaszi szünet |
11. hét |
április 28. |
A maximális folyam feladat, 2. rész (9. fejezet): a javítóutas algoritmus vizsgálata (9.2. fejezet) (eddig tart a zárthelyi anyaga), egészértékűségi lemma (9.17. lemma) |
április 29. |
11. gyakorlat |
12. hét |
május 5. |
A maximális folyam feladat, 3. rész (9. fejezet): a folyamprobléma változatai (9.3. fejezet); Diszjunkt utak, többszörös összefüggőség, 1. rész (10. fejezet): éldiszjunkt utak (10.1. fejezet) |
18:00 Zárthelyi: Feladatok és pontozási útmutató
|
május 6. |
12. gyakorlat |
13. hét |
május 12. |
Diszjunkt utak, többszörös összefüggőség, 2. rész (10. fejezet): pontdiszjunkt utak (10.2. fejezet), többszörös összefüggőség (10.3. fejezet) |
18:00 Pótzárthelyi: Feladatok és pontozási útmutató
|
május 13. |
13. gyakorlat |
14. hét |
május 19. |
Legrövidebb utak (11. fejezet): Bellman–Ford-algoritmus (11.1. fejezet, algoritmus vetítés) |
május 20. |
14. gyakorlat |
– |
június 4. |
10:00 Pótpótzárthelyi
|