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
VIMA0175 2. 2/0/0/f 2 2/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

Feladatok megoldása az alábbi témákban: 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)

gyakorlat

10. Követelmények

a. A szorgalmi időszakban: Az elégséges gyakorlati jegy feltétele mindkét félévközi zárthelyi legalább elégséges szinten való megírása. A végső gyakorlati jegy megállapításakor a két zárthelyi eredményén kívül a házi feladatokban és az órai szereplésben nyújtott teljesítményt is figyelembe vesszük.

b. A vizsgaidőszakban: -

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

vima0175gy.rtf

egy. tanár

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