Tárgy neve: Gráfelmélet ea. (informatikus)

Tanszék: Halmazelmélet és Matematikai Logika Tanszék

Tematika:
1. Összefüggőség, fák, éltesztelés. Fokszámsorozatok, fák összeszámlálása, Cayley- tétel, Prüfer-kódolás. 2. Folyamok, MFMV-tétel, Ford-Fulkerson algoritmus, Menger-tételek. 3. Páros gráfok párosításai, permanens, véletlen algoritmus, Schwartz-lemma. Párosítások tetszőleges gráfokban. Tutte-tétel, Berge-formula, Edmonds-algoritmus. 4. A kínai postás problémája, Hamilton-út és Hamilton-kör (Dirac, Ore), utazó ügynök probléma. 5. Csúcs-és élszínezés, mohó algoritmus, Vizing-tétel, Brooks-tétel, Gallai-Roy-Vitaver-tétel. 6. Klikkek és független halmazok, Caro-Wei, Turán-tétel, Ramsey-elmélet, Schur-tétel. 7. Kisvilág gráfokról röviden. 8. Párhuzamos algoritmusok, elosztott számítások és gráfelmélet.

Előadás kódja: MMN101piE, óraszám: 2, kredit: 3

Gyakorlat kódja: MMN101piG, óraszám: 1, kredit: 1