Diszkrét matematika előadás, 2015/2016 ősz

Kedd 16:00-18:00, Kerékjártó Béla terem

KÖVETELMÉNYEK

Az előadás teljesítésének előfeltétele a gyakorlaton megszerzett aláírás (a gyakorlat követelményrendszere itt olvasható).

Az előadás anyaga egy 50 pontos vizsgán lesz számon kérve a vizsgaidőszakban (az ETR-ben meghirdetett időpontokban), mely egy írásbeli beugróból és egy tételhúzásos szóbeli feleletből áll.
A beugró a tananyag fő fogalmainak, tételeinek ismeretét és MEGÉRTÉSÉT teszteli; amennyiben itt komoly hiányosságokra derül fény, az érdemjegy szóbeli vizsga nélkül elégtelen.
A szóbeli vizsga két részből áll: Először segédanyagok használata nélkül ismertetni kell a kihúzott téma fő tételeit és a szükséges fogalmakat. Ha ez nem sikerül elfogadható szinten, akkor elégtelen a vizsga. Ezután következik a bizonyítások részletezése, melynek kidolgozásához összesen legfeljebb 5 percig bármilyen írott segédanyagba beleolvashatunk (gondolkodás nélkül lemásolni nem lehet). Ezt az 5 percet tetszőleges módon beoszthatjuk, legfeljebb 3 részletre osztva. (Természetesen a szóbeli felelet előtt ennél jóval több felkészülési idő lesz összességében, ez az 5 perc csak a segédanyagok használatára vonatkozik.)

Az előadásvizsgán elért pontszámhoz hozzáadódik a gyakorlatról hozott pontszám (a gyakorlaton is legfeljebb 50 pontot lehet szerezni). Az így kialakult összpontszám határozza meg az érdemjegyet (ha a korábbi bekezdések másképp nem rendelkeznek):
  0 – 50:   elégtelen
51 – 60:   elégséges
61 – 70:   közepes
71 – 85:   jó
86 – 100: jeles

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, illetve általam kiadott szorgalmi feladatok otthoni megoldásával. A pluszpontok hozzáadódnak a fent kialakult összpontszámhoz.

TEMATIKA

A kötelező anyagon felüli "szorgalmi" témákat zöld szín jelöli.

1. Fokszámsorozatok: Számsorozatok realizációja tetszőleges gráffal, hurokélmentes gráffal, illetve egyszerű gráffal. Havel—Hakimi-algoritmus (lásd 1. gyakorlat). Erdős—Gallai-tétel kimondása (lásd 1. gyakorlat). Számsorozatok realizációja fával.
2. Feszítőfák összeszámlálása: Cauchy—Binet-formula (bizonyítás nélkül). Cayley-tétel. Kirchhoff-formula. Prüfer-kód. Adott fokszámsorozatú fák száma.
3. Párosítások páros gráfokban: Páros gráf BG páros-szomszédsági mátrixa. BG permanensének és determinánsának, valamint az XG polinommátrix determinánsának kapcsolata a G-beli teljes párosítások létezésével/számával. Schwartz-lemma (bizonyítás nélkül). Véletlen algoritmus teljes párosítás létezésének tesztelésére. A ν(G) paraméter definíciója. Javító utak és javítóút-kezdemények, párosítás javítása. Kőnig-akadály. Magyar módszer. Kőnig—Hall-tétel (ismétlés).
4. Párosítások általános gráfokban: A ν(G) paraméter definíciója. Javító utak és javítóút-kezdemények, párosítás javítása. Tutte-akadály, Tutte-tétel. Berge-formula. Edmonds-algoritmus.
5. Élszínezések: Jó élszínezés, élkromatikus szám definíciója. Páros gráfok élkromatikus száma. Kempe-átszínezés. Vizing-tétel. Shannon-tétel (bizonyítás nélkül). Kétszeresen élösszefüggő 3-reguláris síkgráfok élkromatikus számának levezetése a négyszín-tételből (+ a négyszín-tétellel való ekvivalencia másik irányának bizonyítása).
6. Csúcsszínezések: Derékbőség definíciója. Nagy kromatikus számú, nagy derékbőségű gráfok. Hajós-konstrukció.
7. Folyamok: Hálózat, megengedett folyam, folyamérték definíciója. Vágás, vágás kapacitása. "Anyagmegmaradási" lemma. Javító utak, javítóút-kezdemények, folyam javítása. Maximális folyam, minimális vágás tétel. Ford—Fulkerson-algoritmus. Egész élkapacitású hálózatok.
8. Többszörös összefüggőség: k-szoros élösszefüggőség és összefüggőség definíciója, és a közöttük lévő kapcsolatok. Egy U ponthalmaz határa, k-szoros élösszefüggőség definíciója e fogalom segítségével. Menger-tételei (többszörös összefüggőségre, és "lokális" változatok). Kétszeresen élösszefüggő és összefüggő gráfok struktúratétele (bizonyítás nélkül). Élösszehúzás. Háromszorosan összefüggő gráfokra vonatkozó lemma (bizonyítás nélkül). Síkgráf tartományainak határának jellemzése összefüggő, kétszeresen élösszefüggő, illetve kétszeresen összefüggő gráfok esetén (bizonyítás nélkül).
9. Síkgráfok: K5 és K3,3 nem síkgráfok. Topologikus részgráfok, minorok; a közöttük lévő kapcsolatok. Kuratowski-tétel (csak az egyszerűbb irány bizonyítása). Wagner-tétel (a nehéz irányból az öf. és 2-öf. esetek bizonyítása nem kell).
10. Metszési szám: Metszési szám definíciója, példák. Könnyű alsó becslés egyszerű gráf metszési számára (az Euler-formula következményéből). Metszési lemma. Szemerédi—Trotter-tétel.
11. Extremális gráfelmélet: ex(n, R) paraméter. Turán-gráfok. Turán-tétel. Mantel-tétel. Erdős—Stone-tétel (bizonyítás nélkül). Egy adott fát nem tartalmazó gráfok (bizonyítás nélkül). C4-mentes gráfok.
12. Ramsey-elmélet: Ramsey-tétel, Ramsey-számok (+ általánosítás több színre, illetve részhalmazok színezésére). Schur-tétel. Erdős—Szekeres-tétel (Happy end probléma).

SEGÉDANYAGOK, KIVETÍTETT PREZENTÁCIÓK

A fő segédanyag a korábbi előadó, Hajnal Péter elektronikus jegyzete a kurzushoz: 2014/2015-ös tanév
5. előadás: Párosítási algoritmusok + Hajnal Péter részletes jegyzete
6. előadás: Élszínezések
9. előadás: Ford—Fulkerson-algoritmus szemléltetése: kivetített prezentáció + Hajnal Péter jegyzetében (9. oldal, azonosan 0 folyamból indulva, a Gf segédgráf felrajzolása nélkül).
A Kombinatorika BSc előadás jegyzete (ismétlés)
Fák ekvivalens definíciói (ismétlés)

AJÁNLOTT IRODALOM

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ó)
Benny Sudakov: Graph Theory (internetes jegyzet)
Friedl Katalin, Recski András, Simonyi Gábor: Gráfelméleti feladatok (Typotex)

HASZNOS LINKEK

A gyakorlat honlapja

Főoldal