Kombinatorika és gráfelmélet 1.

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

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
VIMA0173 1. 2/1/0/v 4 1/1
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
Ajánlott:

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

Neptun-kód Cím --

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

Elemi leszámlálás: Permutációk, kombinációk, variációk, skatulya-elv, szita-módszer. Fák, minimális költségű feszítő fa. Kruskal algoritmus, Prüfer-kód, Cayley-tétele, Ruler-bejárás. A “kínai postás” probléma. Dirac-Erdős-Pósa-Chvatal tételei. Páros gráfok. König-Hall tétel. Tutte és Petersen tételei. Maximális folyamok: Menger és Ford-Fulkerson tételek. Pont- és élszínezés (alsó és felső korlátok, Mycielski-konstrukció, Broks- és Vízing tétel).

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

előadás és gyakorlat

10. Követelmények

a. A szorgalmi időszakban: 2 zárthelyi minimum elégséges szinten történő teljesítése

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

egy. tanár

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