Gráfelmélet/Kombinatorika mester szakosok számára

• Amit a kurzusról tudni kell
• Amit a vizsgáról tudni kell
• Tematika
• Mintavizsga kérdések

• Fokszámsorozatok realizációja
  • Dombi Péter jegyzete   pdf file
  • Domanovszki Bettina jegyzete   pdf file

• Fák összeszámlálása: Cayley-tétel adott n elemû ponthalmazon lévõ fák számára, Kirchoff-formula adott egyszerû gráf feszítõfáinak számára, Binet-Cauchy-tétel
  • Körmendi Kristóf jegyzete   pdf file
  • Palatinus Endre jegyzete   pdf file

• Folyamok:    alapfogalmak,   elmélet,   algoritmusok.
  • Krizsán Lívia jegyzete   pdf file
  • Pék Máté jegyzete   pdf file

• k-szorosan élösszefüggõ gráfok, ponthalmazok határa, minimálisan k-szorosan összefüggõ gráfok, k-szorosan összefüggõ gráfok növekedése
  • Kertész Balázs jegyzete   pdf file
  • Magyari Nikolett jegyzete   pdf file

• Lovász-lemma bizonyítása, Menger-tételei, k-szorosan (pont) összefüggõ gráfok, párosítások, Kõnig-tétele
  • Kapusi Csilla Andrea jegyzete   pdf file
  • Gulyás Gergely jegyzete (jpg file-ok)   1. oldal    2. oldal    3. oldal    4. oldal    5. oldal    6. oldal    7. oldal    8. oldal
  • Majoros György jegyzete   pdf file

• Algoritmikus kérdések páros gráfok párosításaira, Schwartz-lemma, véletlen algoritmus teljes párosítás létezésének tesztelésére, lineáris programozási módszer, párosítási politop
  • Bittner Emese jegyzete   pdf file

• Kombinatorikus/javításos módszer, javító utak Javító utak mohó keresése
• Párosítások (általános) gráfokban, Javításos párosítás keresés: Edmonds-algoritmus
  • Illes László jegyzete   pdf file

• Edmonds-algoritmus helyessége, Párosítási struktúra-tételek, Alkalmazás: Petersen-tétel
  • Provits Milán jegyzete   pdf file

• Élszínezések. 3-reguláris, kétszersen élösszefüggõ síkgráfok élszínezései, 4-szín-tétel és térképek színezése, dualitás, páros gráfok élszínezései, él-kromatikus száma és maximális fokszám kapcsolata
  • Szabó Tamás jegyzete   pdf file

• Vizing-tétel bizonyítása. k színnel nem színezhetõség karakterizációja, Hajós-tétel.
  • Dohány Péter jegyzete   pdf file

• Nagy kromatikus számú, nagy derékbõségû gráfok
• Síkgráfok, tartományok határa, Euler tételei, Minorok, topológikus részgráfok
  • Ozsvárt László jegyzete   pdf file
  • Udvari Balázs jegyzete alapján (Egy kissé részletesebb mint az elõadás)   pdf file

• Wagner-tétel bizonyítása, metszési szám
  • Jegyzet (egy kissé részletesebb mint az elõadás)   pdf file

• Szomszédsági mátrix és sajátértékei
  • Jegyzet (egy kissé részletesebb mint az elõadás)   pdf file

    Ha az elõadással, gyakorlattal kapcsolatban bármilyen kérdés, megjegyzés, vélemény stb. felmerül, akkor azokat az hajnal@math.u-szeged.hu email címen érdeklõdve várom.