Gráfelméleti alapfogalmak. Euler-utak, Euler-körök. Hamilton-utak és Hamilton-körök, létezésük szükséges feltételei: pontok törlése után keletkező komponensek maximális száma. Elégséges feltételek: Dirac és Ore tételei. A legrövidebb út keresésének problémája (mint gyakorlati probléma).
Szélességi bejárás, a legrövidebb út keresésének megoldása élsúlyozatlan esetben. Az élsúlyozott eset, Dijkstra, Ford, Floyd algoritmusai.Hálózati folyamfeladatok (mint gyakorlati problémák). Vágások, és kapacitásaik. Javitó út, Ford-Fulkerson tétel, Edmonds-Karp tétel, egészértékűségi lemma. Menger tétele az adott csúcsok között futó éldiszjunkt utak maximális számáról.Az erőforrás-hozzárendelési probléma (mint gyakorlati
probléma). Páros gráfok és a kromatikus szám fogalma, páros gráfok jellemzése páratlan hosszú körökkel. Moho színezés. Párosítások,
maximális, illetve teljes párosítások fogalma. Maximalis párosítas keresése páros gráfokban: javító utak, König tétele a maxi mális párosítás és minimális lefogó ponthalmaz méreteinek kapcsolatáról. Tutte tétele (a szükségesség bizonyításával, az elégségesség bizonyítása opcionális; a rendelkezésre álló időtől függ).Térképszínezési feladat (mint "gyakorlati" probléma). Gráfok duálisa, élgráfja. Kromatikus sz ámok becslései: maximális fokszám, maximális klikk-méret, Mycielski-konstrukció. Síkba, gömbfelületre, térbe rajzolhatóság (mint gyakorlati probléma). Sztereografikus projekció. Euler poliéder-tétele. Síkba rajzolható gráfok kromatikus számairól (példa 3-kromatikus síkgráfra, 6-szín tétel, 5-szín tétel). Eseményalgebra, valószínűségi algebra, Valószínűségi változók, Nagy számok törvénye, Centrális határeloszlás-tétel. Sztochasztikus folyamatok. Markov-láncok, Markov folyamatok. Speciális sztochasztikus folyamatok a műszaki rendszerek jellemzésében: Poisson-folyamat, rekurrens folyamat, szemi-Markov folyamat. Wiener-Hincsin összefüggéspár, ergodicitás.