Kombinatorika és gráfelmélet 2.

A tantárgy angol neve: Combinatorics and Graph Theory 2.

Adatlap utolsó módosítása: 2006. július 1.

Tantárgy lejárati dátuma: 2015. január 31.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

TTK

Alkalmazott matematikus szak

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VIMA0174 2. 2/0/0/v 3 2/2
3. A tantárgyfelelős személy és tanszék Dr. Recski András, Számítástudományi és Információelméleti Tanszék
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 rendek grafikus formában itt láthatók.

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