MMN001E, MMN101E, MMN141E

DISZKRÉT MATEMATIKA

GRÁFELMÉLET

GRÁFELMÉLET ELEMEI

2011 Õsz

Elõadások Szeptember 7.:

I. Fokszámsorozatok realizációja. Fák összeszámlálása
- Elsõ témakör jegyzete pdf file

Szeptember 14.:

I. Fák összeszámlálása (folytatás): Kirchoff-formula adott hurokélnélküli gráf feszítõfáinak számára.
II. Gráfok magasabbfokú összefüggõsége. Folyamok.
- Második témakör jegyzete pdf file

Szeptember 21.

II. Folyamok (folytatás): Javító utak, Alaptétel és következményei.

Szeptember 28.

II. A folyamok elméletének következményei: Menger tételei, magasabb fokú összefüggõség jelemzései.

Október 5.

III. Minimális k-szorosan élösszefüggõ gráfok. Lovász leemelési lemmája és következményei.
- Harmadik témakör jegyzete pdf file

Október 12.

IV. Párosítások: Mohó algoritmus, véletlen algoritmusok.
- Negyedik témakör jegyzete pdf file

Október 19.

IV. Párosítások: Javító utas algoritmusok.

Október 26.

IV. Párosítások: Edmonds-algoritmus.

November 2. Õszi szünet, Halottak napja

November 9.

V. Színezések: Élszínezések (4-szín-tétel és síkgráfok élszínezései, él-kromatikus szám és maximális fokszám kapcsolata, Vizong-tétel)
- Ötödik témakör jegyzete pdf file

November 16.

V. Színezések: Csúcsszínezések, Nagy kromatikus számú, nagy derékbõségû gráfok

November 23.

V. Színezések: Csúcsszínezések, k színnel nem színezhetõség karakterizációja, Hajós-tétel.
VI. Síkgráfok: Síkgráfok, minorok, topológikus részgráfok, nem síkgráfok.
- Hatodik témakör jegyzete pdf file

November 30.

VI. Síkgráfok: Wagner-tétel bizonyítása Metszési szám, metszési lemma.

December 7.

VI. Síkgráfok: Metszési lemma alkalmazása
VII. Klikkek: Turán-tétel, Extremális gráfelmélet
- Hetedik témakör jegyzete pdf file

December 14.

VII. Klikkek: Ramsey-számok, Aritmetikai Ramsey-elmélet

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.