SEGÉDANYAGOK
1. MINTAVIZSGA, 2. MINTAVIZSGA, 3. MINTAVIZSGA
TEMATIKA
A zölddel jelölt témák nehezebbek, és a jobb jegyért várom el őket;
ezekkel akkor foglalkozzunk, ha az anyag többi része már jól megy.
AMIT A VIZSGÁRÓL TUDNI KELL
A vizsga írásbeli lesz, a fenti tematikából válogatott elméleti kérdésekkel, illetve a fogalmak és tételek megértését tesztelő egyszerű feladatokkal.
Csak azokat a tétel-bizonyításokat kell ismerni, amelyek szerepeltek előadáson (vagy házi feladatnak lettek feladva), körülbelül olyan mélységben, ahogy elhangzottak.
A csillaggal jelölt állítások nehezebbek, ezek bizonyítását csak a jobb jegyért várom el; illetve a hosszabb bizonyításokból jellemzően csak egy kis részre kérdezek rá.
Az órákon pluszpontokat is lehet szerezni az előadást kiegészítő feladatok írásos megoldásával (5 pontot ér egy ilyen feladat megoldása).
AJÁNLOTT IRODALOM
Hajnal Péter: Gráfelmélet (Polygon Jegyzettár)
2010/2011 tanév (Hajnal Péter honlapján)
2009/2010 tanév (Hajnal Péter honlapján)
2. Összefüggőség: Séta, vonal, út, összefüggőség; az összefüggőség tesztelése (a szomszédsági mátrix hatványainak jelentése)
3. Fák: Fák ekvilalens definícói, feszítőfák; feszítőfák száma (Kirchhoff-formula*, Cayley-tétel), Cauchy-Binet formula (bizonyítás nélkül)
4. Párosítások I.: Párosítás, teljes párosítás, páros-szomszédsági mátrix fogalma; véletlen algoritmus teljes párosítás létezésének tesztelésére páros gráfokban, Schwartz-lemma (bizonyítás nélkül)
5. Vonalak: Vonal, Euler-(kör)vonal; Euler tétele, kínai postás problémája
6. Hamilton-út, Hamilton-kör, mohó és csavart útnövelés, Dirac tétele; utazóügynök probléma, 2-approximációs algoritmus a relaxált változatra
7. Folyamok: A folyamprobléma, javító utak, javító út-kezdemények, maximális folyam-minimális vágás tétel, Ford-Fulkerson algoritmus
8. Magasabb összefüggőség: k-szorosan élösszefüggő és összefüggő gráfok, Menger-tételei (a pontösszefüggő változatot csak kimondani kell tudni)
9. Párosítások: Javító utak, javító út-kezdemények; párosítási tételek és algoritmus páros gráfokban: Kőnig-akadály, Kőnig-Hall-tétel, magyar módszer; Tutte-akadály, Tutte-tétel (bizonyítani csak az egyszerű irányát kell)
10. Csúcsszínezések: Jó színezés, kromatikus szám fogalma; páros gráfok jellemzése; mohó színezési algoritmus; kromatikus szám felső becslése a maximális fokszámmal, Brooks-tétel (bizonyítani csak a nem reguláris gráfokra vonatkozó speciális esetet kell)
11. Síkgráfok: Szép lerajzolás, síkgráf definíciója; tartományok; síkra rajzolt gráf duálisának fogalma; Euler tétele (és következményei: egyszerű síkgráfok élszámára vonatkozó felső becslés, hatszín-tétel, K_5, K_{3,3} nem síkgráfok); gráfok felosztása, Kuratowski-tétel (bizonyítani csak az egyszerű irányát kell); négyszín-tétel (csak kimondani)
12. Klikkek és független ponthalmazok: A két fogalom kapcsolata; kromatikus szám alsó becslése ω(G)-vel; nagy kromatikus számú háromszögmentes gráfok; mohó és módosított mohó algoritmus független ponthalmaz keresésére, α(G) alsó becslése a maximális fokszám illetve átlagfokszám segítségével; Turán-gráfok, Turán tétele
(folyamatosan bővül)
A gyakorlat aláírásának a legalább elégséges vizsgajegy a feltétele.
Osztályzat:
0-50 pont: elégtelen
50-60 pont: elégséges
60-70 pont: közepes
70-85 pont: jó
85-100 pont: jeles
Lovász László: Kombinatorikai problémák és feladatok (Typotex, online verzió)
Friedl Katalin, Recski András, Simonyi Gábor: Gráfelméleti feladatok (Typotex)