BME VIK - Kombinatorika és gráfelmélet 2.

3. A tantárgyfelelős személy és tanszék Dr. Recski András,

4. A tantárgy előadója

Név:	Beosztás:	Tanszék, Int.:
Dr. Simonyi Gábor	egy. docens	Számítástudományi és Információelméleti Tanszék

5. A tantárgy az alábbi témakörök ismeretére épít

6. Előtanulmányi rend

Kötelező:

TárgyEredmény( "BMEVIMA0173" , "jegy" , _ ) >= 2

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

Ajánlott:

Kombinatorika és Gráfelmélet 1. (bmevima0173)

Tematikaütközés miatt a tárgyat csak azok vehetik fel, akik korábban nem hallgatták a következő tárgyakat:

bmevima1824 Kombinatorika és Gráfelmélet II.

7. A tantárgy célkitűzése

Bevezetés a diszkrét matematika elemeibe és módszereibe.

8. A tantárgy részletes tematikája

Szélsőérték-problémák, extrém gráfok: Turán-típusú tételek, Erdős-Gallai tételek. Ramsey-számok, Erdős-Szekeres tétel. Síkbarajzolhatóság (Euler-formula, Kuratowski, Wagner és Fáry tételei). Adjacencia-, incidencia-, kör- és vágatmátrix. Duálgráfok, 2-izomorfia, Whitney tételei. Ötszíntétel, Tait tétele. Perfekt gráfok, listaszínezés. Gráfok spektruma. Rekurziók és generátorfüggvények: Fibonacci számok, Stirling számok, Bell-számok, számelméleti partíciók, Catalan számok. Lineáris- és másodrendű rekurziók. Extremális halmazrendszerek. Erdős-Ko-Rado tétel. Sperner-rendszerek.

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

: előadás

10. Követelmények

a. A szorgalmi időszakban: A vizsgára bocsátás feltétele a legalább elégséges gyakorlati jegy (bmevima0175)

b. A vizsgaidőszakban: szóbeli vizsga

c. Elővizsga: -

13. Jegyzet, tankönyv, felhasználható irodalom

Katona Gyula, Recski András: Bevezetés a véges matematikába, 1993

15. A tantárgy tematikáját kidolgozta

Név:

Beosztás:

Tanszék, Int.:

Dr. Recski András

vima0174ea.rtf

egy. tanár

Számítástudományi és Információelméleti Tanszék