Az előadás teljesítésének előfeltétele a teljesített gyakorlat (a gyakorlat követelményrendszere itt olvasható).
Az előadás anyaga egy 100 pontos írásbeli vizsgán lesz számon kérve a vizsgaidőszakban (az ETR-ben meghirdetett időpontokban), mely a tematikából válogatott elméleti kérdéseket, illetve a fogalmak és tételek megértését tesztelő egyszerű feladatokat tartalmaz majd. A vizsga sikeres teljesítésének alapvető feltétele az alapfogalmak és legegyszerűbb összefüggések pontos ismerete, ezek hiányában a vizsga automatikusan elégtelen.
A félév folyamán pluszpontokat is lehet szerezni (legfeljebb 10-et) az előadás alatt tett érdemi hozzászólással/hibajelzéssel. A pluszpontok hozzáadódnak a vizsgán szerzett pontszámhoz.
Ponthatárok:
0 – 50: elégtelen
51 – 60: elégséges
61 – 70: közepes
71 – 85: jó
86 – 100: jeles
1. MINTAVIZSGA, 2. MINTAVIZSGA, 3. MINTAVIZSGA (Ezek egy régebbi kurzus tananyagához lettek készítve, csak a struktúrát szemléltetik.)
2009/2010 tanév elektronikus jegyzete (Hajnal Péter honlapján)
2010/2011 tanév elektronikus jegyzete (Hajnal Péter honlapján)
Ford—Fulkerson-algoritmus
Párosítási algoritmusok
Fák ekvivalens definíciói (ismétlés)
1. Fokszámsorozatok: Számsorozatok realizációja tetszőleges gráffal, illetve egyszerű gráffal. Havel—Hakimi-algoritmus.
2. Feszítőfák összeszámlálása: Cayley-tétel. Prüfer-kódolás. Adott fokszámsorozatú fák száma.
3. Folyamok: Hálózat, megengedett folyam, folyamérték definíciója. Vágás és kapacitása. Maximális folyam - minimális vágás tétel. Javító utak,
javítóút-kezdemények. Ford—Fulkerson-algoritmus.
4. Többszörös összefüggőség: k-szoros élösszefüggőség és összefüggőség definíciója, és ezek kapcsolata. Menger tételei.
5. Párosítások: Párosítások és a ν(G) paraméter definíciója. Javító utak és javítóút-kezdemények. Kőnig-akadály.
Kőnig—Hall-tétel. Magyar módszer. Tutte-akadály. Tutte-tétel. Edmonds-algoritmus.
6. Élszínezések: Jó élszínezés, élkromatikus szám definíciója. Páros gráfok élkromatikus száma. Vizing-tétel (bizonyítás nélkül). Shannon-tétel (bizonyítás nélkül). A teljes gráfok élkromatikus száma.
7. Csúcsszínezések: Jó csúcsszínezés, kromatikus szám definíciója. Páros gráfok jellemzése (bizonyítás nélkül). Mohó színezési algoritmus.
Kromatikus szám felső becslése a maximális fokszám segítségével. Brooks-tétel (bizonyítás nélkül). Klikkek; az ω(G) paraméter és kapcsolata a kromatikus számmal.
8. Síkgráfok: Síkgráfok definíciója. Kuratowski-tétel (bizonyítás nélkül). Négyszín-tétel (bizonyítás nélkül).
9. Hamilton-utak, Hamilton-körök: Hamilton-út, Hamilton-kör definíciója. Dirac-tétel.
10. Kínai postás problémája: Euler-körvonal, Euler-tétel. Kínai postás problémája.
Hajnal Péter: Gráfelmélet, II. kiadás (Polygon Jegyzettár)
Lovász László: Kombinatorikai problémák és feladatok (Typotex, interneten is olvasható)
Reinhard Diestel: Graph Theory (Springer-Verlag, interneten is olvasható)
Friedl Katalin, Recski András, Simonyi Gábor: Gráfelméleti feladatok (Typotex)
| ⇦ | Főoldal |