1. elöadás (szept 13.)

Königsbergi hidak
Sperner lemma (két biz)
Sylvester sejtés - Gallai tétel

2. elöadás (szept 20.)

Véges es végtelen közötti kapcsolat: a König lemma.
Összefüggöségi algoritmusok I: szélességi keresés.
Alsó becslés: a ,,rosszindulatú manó".

3. elöadás (szept 27.)

Ramsey tétele gráfokra. Binomiális felsö becslés.
Erdös alsó becslése R(k,k)-ra.
Végtelen Ramsey gráfokra. Kapcsolata a végessel.

4. elöadás (okt 4.)

Ramsey tételek halmazrendszerekre. (Végtelen es véges.)
Alkalmazás: a ,,happy end" probléma.
K(t) es F(k,l) létezése; binomiális felsö becslés(ek).

5. elöadás (okt 11.)

A ,,happy end" probléma (folytatás):
F(k,l) pontos értéke;
alsó becslés K(t)-re.
Páros (,,kétosztályú") gráfok.
A ,,házassag-probléma".
A bizottsági elnökök problémája.
Hall feltétele.
A König-Hall tétel (,,alternáló utak" módszere).

6. elöadás (okt 18.)

Páros (,,kétosztályú") gráfok (folytatás).
A ,,házasság-probléma" megoldása.
A König-algoritmus: ,,alternáló szélességi keresés".
Sikbarajzolható gráfok.
Az Euler-összefüggés. Élszám-korlátok.
A duális gráf.
A hat- es ötszintétel.

7. elöadás (okt 25.)

Minimális költségü feszitö fa
A ,,mohó" algoritmus
Rész-feladat: rendezés n log n idoben.

8. elöadás (nov 8.)

Minimális költségü feszitö fa (folytatás)
Az ,,unio-holvan" feladat;
megoldasa O(n log n) idöben (van jobb is!).
Legrövidebb utak keresése
A Dijkstra-algoritmus;
megvalósitása O(m+n2) idöben;
megvalósitása ,,kupacokkal" O( (m+n) log n ) idöben.

9. elöadás (nov 15.)

Turán tétele.
Alkalmazás: a maximálishoz közeli távolságok száma.
(Volt a max. távolságok száma is.)

10. elöadás (nov 22.)

Véges geometriák alaptulajdonságai és létezése; ortogonális latin négyzetek létezése.
A C4 nélkuli gráfok maximális elszáma.

11. eloadás (nov 29.)

A szita-módszer.
A tizenkét feladat(ból tiz :).
Stirling számok.

12. eloadás (dec 6.) ZH!

13. eloadás (dec 13.)

Gráfok szinezései
Nagy kromatikus háromszögmentes gráf.
Végtelen gráfok kromatikus száma.
Brooks tétele.

Gyorgy Elekes
Last modified: Fri Jan 5 09:52:39 CET 2007