MBX785E (régen Mx785)

Gráfelmélet

2009 Ősz

 

  • Előadások:
    • Szeptember 8.:
    TUDNI KELL
    • Egyszerű gráf fogalma
    • Gráf fogalma
    • Fokszám fogalma
    • Séta fogalma
    • Vonal fogalma
    • Út fogalma
    • Sétálás
    • Mohó vonalnövelés
    • Mohó út növelés
    • Egyszerű gráf szomszédsági mátrixa

    Szeptember 15.

    TUDNI KELL
    • Elérhetőség reláció fogalma
    • Összefüggő gráf fogalma
    • Pontok, élek elhagyása egy gráfból
    • Komponens fogalma
    • Fa fogalma
    • Feszítőfa fogalma
    • Kör fogalma

    Szeptember 22.

    TUDNI KELL
    • Ághajtás operáció és kapcsolata a fákkal
    • Gyökeres fa
    • Euler-vonal

    Szeptember 29.

    TUDNI KELL
    • Vonal betoldásos növelése
    • Mi a kínai postás probléma inputja és mi az outpuja?
    • Hamilton-út és Hamilton-kör fogalma

    Október 6.

    TUDNI KELL
    • Út mohó és csavarásos növelése
    • Mi az utazó ügynök probléma inputja és mi az outpuja?

    Október 13.

    TUDNI KELL
    • Egy gráf színezésének, jó színezésének fogalma.
    • Egy gráf kromatikus száma.
    • Mi akadályozhatja meg egy gráf jó 2-színezhetőségét?
    • Mohó színezési algoritmus.

    Október 20.

    TUDNI KELL
    • Egy színezés Kempe-átszínezése.
    • Klikk fogalma.
    • Egy gráf omega paramétere.
    • Az omega paraméter és a kromatikus szám közti kapcsolat.

    Október 27. Őszi szünet

    November 4.

    TUDNI KELL
    • Párosítás fogalma.
    • Teljes párosítás fogalma.
    • A nü paraméter.
    • Lefogó ponthalmaz fogalma.
    • A tau paraméter.
    • A nu és tau paraméter közöti kapcsolat.
    • Javító út fogalma egy párosításra nézve.
    • Miért javít egy javító út?

    November 11.

    TUDNI KELL
    • Kőnig-akadály fogalma
    • Mit akadályoz meg egy Kőnig-akadály?
    • Mit mondhatunk egy párosítás méretéről (természesen egy páros gráfban), ha van egy Kőnig-akadály?

    November 18.

    TUDNI KELL
    • Ha a mohó javító út keresés sikertelen, akkor biztos nincs javító út?
    • Tutte-akadály fogalma.
    • Mit akadályoz meg egy Tutte-akadály?
    • Mit mondhatunk egy párosíta's méretéről, ha van egy Tutte-akadályunk?

    November 25.

    TUDNI KELL
    • Független ponthalmaz fogalma.
    • Alfa paraméter.
    • Komplementer gráf fogalma.
    • Független ponthalmazok, klikkek és lefogó ponthalmazok kapcsolata.
    • Mohó algoritmus független ponthalmaz keresésére.
    • Módosított mohó algoritmus független ponthalmaz keresésére.
    • n pontú k részes Turán-gráf fogalma.
    • Turán-gráf legnagyobb klikkjének mérete.
    • Turán-tétel kimondása

    December 2.

    TUDNI KELL
    • Monokromatikus ponthalmaz egy piros-kék élszínezett teljes gráfban.
    • Ramsey-számok fogalma.
    • Ramsey-tétel.

        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.