Tantárgy kódja

MTO1106

Tantárgy neve

Kombinatorika és gráfelmélet

Tantárgy angol neve

Combinatorics and Graph Theory

Kredit

3

Félévi követelmény

Gyakorlati jegy

Heti óraszám

1 + 2

Elmélet + Gyakorlat

Ajánlott félév

2

Cél

A kombinatorika és a gráfelmélet itt tárgyalt kérdéseinek egy része szerepel az általános és középiskolai oktatásban is, és hozzátartozik az általános matematikai alapműveltséghez. Ezek készségszintű ismerte elvárható a hallgatóktól.

Cél angol

The course gives basic skills and knowledge of mathematics. The problem solving methods discussed in this course are used in elementary and secondary education, as well.

Tartalom

Binomiális és polinomiális tétel. Alapvető leszámlálási eljárások. Szitaformula. Generátorfüggvények módszere. Rekurzív sorozatok. Gráfelméleti alapfogalmak. Speciális gráfok, tulajdonságaik. Gráfok színezése, az ötszíntétel. Páros gráfok és független élrendszerek, párosítási algoritmusok, Kőnig tétele. Euler-vonal, Hamilton-kör. Síkba rajzolható gráfok jellemzése. Fák, Kruskal-algoritmus. Lineáris algebra és gráfok. Algoritmikus és bonyolultsági kérdések a kombinatorikában és gráfelméletben. A kombinatorika és a gráfok az általános iskolában. Stratégiás játékok.

Tartalom angol

COMBINATORICS: the pigeonhole principle; counting principles; permutations and combinations; identities involving binomial coefficients; the inclusion-exclusion principle; recurrence relations; generating functions. GRAPH THEORY: graphs and their basic components; directed and undirected graphs; isomorphism of graphs; planar graphs; edge- and vertex-colorings; Hamiltonian cycles and the Eulerian graphs; trees; matching theory; digraphs; chromatics number; connectivity of graphs; networks

Számonkérés

Gyakorlati jegy.

Számonkérés angol

term grade

Irodalom

1. Andrásfai Béla: Ismerkedés a gráfelmélettel. Tankönyvkiadó, Budapest, 1985. 2. Hajnal Péter, Elemi kombinatorikai feladatok. Polygon, Szeged, 1997. 3. Lovász László: Kombinatorikai problémák és feladatok, Typotex, Budapest, 1999. 4. Lovász, Pelikán, Vesztergombi: Kombinatorika, Typotex, Budapest, 2003. 5. Urbán János: Kombinatorikai feladatok 14-18 éveseknek, Mozaik, Szeged, 1999. 6. Vilenkin, Kombinatorika, Műszaki Könyvkiadó, Budapest, 1987.

Irodalom angol

1. Richard A. Brualdi,  Introductory Combinatorics, Third Edition, Prentice-Hall, 1999.         2. Béla  Bollobás, Modern Graph Theory, Springer-Verlag, 1998.

Tantárgyfelelős intézet kódja

MII

Tantárgyfelelős oktató

Dr. Lénárd Margit