1. elo"adás (szept 10.)

Königsbergi hidak

Sperner lemma (két biz)

Véges és végtelen közötti kapcsolat: a König lemma.

Sylvester sejtés - Gallai tétel

2. elo"adás (szept 17.)

Összefüggo''ségi algoritmusok, szélességi keresés.

Alsó becslés: a ,,rosszindulatú manó".

3. elo"adás (szept 24.)

Ramsey tétele gráfokra. Binomiális felso" becslés.

Erdös alsó becslése R(k,k)-ra.

Végtelen Ramsey gráfokra.

4. elo"adás (okt 1.)

Végtelen Ramsey kapcsolata a végessel.

Ramsey tételek halmazrendszerekre. (Végtelen és véges.)

Alkalmazás: a ,,happy end" probléma.

K(t) és F(k,l) létezése; binomiális felso" becslés(ek).

5. elo"adás (okt 8.)

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. elo"adás (okt 15.)

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- és ötszíntétel.

7. elo"adás (okt 22. helyett okt 20.)

Minimális költségu" feszito" fa

A ,,mohó" algoritmus

Rész-feladat: rendezés O(n log n) ido"ben.

Az ,,únió-holvan" feladat;

megoldása O(n log n) ido"ben (van jobb is!).

8. elo"adás (november 5.)

Gráfok színezései

Nagy kromatikus háromszögmentes gráf.

Végtelen gráfok kromatikus száma.

Brooks tétele (Lovász bizonyítása).

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

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. elo"adás (nov 19.)

A szita-módszer.

A tizenkét feladat(ból tiz :).

Stirling számok.

11. elo"adás (nov 26.)

Véges geometriák alaptulajdonságai és létezése.

Extremális gráfok. A C₄ nélküli gráfok maximális élszáma.

12. elo"adás (dec 3.) --- zárthelyi

13. elo"adás (dec 10.)

Legrövidebb utak keresése: a Dijkstra-algoritmus.

megvalósitása O(e+n²) ido"ben;

megvalósitása ,,kupacokkal" O( (e+n) log n ) ido"ben.