Diskretna matematika 1

Osnove kombinatoričnega preštevanja:
Osnovna načela preštevanja. Binomski koeficienti, razdelitve, Stirlingova števila 1. in 2. vrste, Bellova števila, Lahova števila, razčlenitve. Dvanajstera pot. Načelo vključitev in izključitev in trdnjavski polinomi. Rekurzivne enačbe, reševanje s pomočjo običajnih rodovnih funkcij, algebra formalnih potenčnih vrst, Catalanova števila.
Osnove teorije grafov:
Osnovne definicije. Homomorfizmi, izomorfizmi in avtomorfizmi grafov. Povezanost. Drevesa in dvodelni grafi. Obhodi in cikli. Eulerjev obhod in Hamiltonov cikel. Ravninski grafi in Eulerjeva formula. Barvanja grafov po vozliščih in po povezavah.

R. J. Wilson, J. J. Watkins: Uvod v teorijo grafov, DMFA-založništvo, Ljubljana, 1997.
J. H. van Lint, R. M. Wilson: A Course in Combinatorics, 2nd edition, Cambridge Univ. Press, Cambridge, 2001.
M. Juvan, P. Potočnik: Teorija grafov in kombinatorika, DMFA-založništvo, Ljubljana, 2000.
D. Veljan: Kombinatorna i diskretna matematika, Algoritam, Zagreb, 2001.

Študent spozna osnovne diskretne strukture in pojme iz kombinatorike ter se seznani z osnovami teorije grafov.

Znanje in razumevanje: Poznavanje osnovnih pojmov iz klasične kombinatorike in iz teorije grafov ter razumevanje osnovnih povezav med njimi. Osnovno znanje natančnega štetja objektov z določenimi lastnostmi iz dane množice.
Uporaba: Uporaba diskretnih matematičnih struktur za predstavitev različnih objektov in procesov. Tovrstne predstavitve so nepogrešljive na primer pri obdelavi podatkov z računalniki.
Refleksija: Povezovanje teoretičnih spoznanj s praktičnimi uporabami na primer v optimizaciji in pri programiranju. Sposobnost prepoznavanja problemov, ki jih lahko uspešno opišemo z diskretnimi matematičnimi modeli.
Prenosljive spretnosti – niso vezane le na en predmet: Poznavanje osnovnih prijemov za delo z diskretnimi matematičnimi strukturami. Natančnost pri razmišljanju in reševanju problemov. Sposobnost prebiranja strokovne literature iz diskretne matematike in sorodnih področij.

Predavanja, vaje, domače naloge, konzultacije

2 kolokvija namesto izpita iz vaj, izpit iz vaj
Izpit iz teorije
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)

Sandi Klavžar:
ILIĆ, Aleksandar, KLAVŽAR, Sandi, RHO, Yoomi. Generalized Lucas cubes. Applicable analysis and discrete mathematics, ISSN 1452-8630, 2012, vol. 6, no. 1, str. 82-94. [COBISS-SI-ID 16242265]
BREŠAR, Boštjan, KLAVŽAR, Sandi, RALL, Douglas. Domination game and an imagination strategy. SIAM journal on discrete mathematics, ISSN 0895-4801, 2010, vol. 24, no. 3, str. 979-991. [COBISS-SI-ID 15648089]
HAMMACK, Richard H., IMRICH, Wilfried, KLAVŽAR, Sandi. Handbook of product graphs, (Discrete mathematics and its applications). Boca Raton, London, New York: CRC Press, cop. 2011. XVIII, 518 str., ilustr. ISBN 978-1-4398-1304-1. [COBISS-SI-ID 15916121]
IMRICH, Wilfried, KLAVŽAR, Sandi, RALL, Douglas F. Topics in graph theory : graphs and their Cartesian product. Wellesley (Mass.): A. K. Peters, 2008. XIV, 205 str., ilustr. ISBN 978-1-56881-429-2. [COBISS-SI-ID 14965081]
Matjaž Konvalinka:
KONVALINKA, Matjaž. Skew quantum Murnaghan-Nakayama rule. Journal of algebraic combinatorics, ISSN 0925-9899, 2012, vol. 35, no. 4, str. 519-545. [COBISS-SI-ID 16250713]
KONVALINKA, Matjaž, PAK, Igor. Geometry and complexity of O'Hara's algorithm. Advances in applied mathematics, ISSN 0196-8858, 2009, vol. 42, iss. 2, str. 157-175. [COBISS-SI-ID 15545945]
KONVALINKA, Matjaž. On quantum immanants and the cycle basis of the quantum permutation space. Annals of combinatorics, ISSN 0218-0006, 2012, vol. 16, no. 2, str. 289-304. [COBISS-SI-ID 16310873]
Marko Petkovšek:
PETKOVŠEK, Marko. Letter graphs and well-quasi-order by induced subgraphs. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2002, vol. 244, no. 1-3, str. 375-388. [COBISS-SI-ID 11414873]
PETKOVŠEK, Marko, ZAKRAJŠEK, Helena. Enumeration of I-graphs: Burnside does it again. Ars mathematica contemporanea, ISSN 1855-3966. [Tiskana izd.], 2009, vol. 2, no. 2, str. 241-262. [COBISS-SI-ID 15497049]
PETKOVŠEK, Marko. Counting Young tableaux when rows are cosets. Ars combinatoria, ISSN 0381-7032, 1994, let. 37, str. 87-95. [COBISS-SI-ID 8048473]
PETKOVŠEK, Marko, WILF, Herbert S., ZEILBERGER, Doron. A=B. Wellesley (Massachusetts): A. K. Peters, cop. 1996. VII, 212 str. ISBN 1-56881-063-6. [COBISS-SI-ID 4085337]
Primož Potočnik:
KNOR, Martin, POTOČNIK, Primož, ŠKREKOVSKI, Riste. The Wiener index in iterated line graphs. Discrete applied mathematics, ISSN 0166-218X. [Print ed.], 2012, vol. 160, iss. 15, str. 2234-2345. [COBISS-SI-ID 16409945]
POTOČNIK, Primož, SPIGA, Pablo, VERRET, Gabriel. Cubic vertex-transitive graphs on up to 1280 vertices. Journal of symbolic computation, ISSN 0747-7171, 2013, vol. 50, str. 465-477. [COBISS-SI-ID 16520537]
POTOČNIK, Primož, SPIGA, Pablo, VERRET, Gabriel. On the nullspace of arc-transitive graphs over finite fields. Journal of algebraic combinatorics, ISSN 0925-9899, 2012, vol. 36, no. 3, str. 389-401. [COBISS-SI-ID 16162137]
JUVAN, Martin, POTOČNIK, Primož. Teorija grafov in kombinatorika : primeri in rešene naloge, (Izbrana poglavja iz matematike in računalništva, 39). Ljubljana: Društvo matematikov, fizikov in astronomov Slovenije, 2000. VI, 173 str., graf. prikazi. ISBN 961-212-105-2. [COBISS-SI-ID 106210560]