Graph Theory lec. (informatikus angol)

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őfeltétel: nincs.

Helyettesítő tárgyak: nincsenek.

Előadás:
Kurzuskód: MMEN101piE Kredit: 3 Óraszám: 2 hetente