Diskretne strukture

Pogojev za vključitev v delo ni.

Izjavni račun. Izjave in izjavni vezniki. Tavtologije in enakovrednost izjavnih izrazov. Disjunktivna in konjunktivna normalna oblika. Polni nabori izjavnih veznikov. Sklepanje.

Predikatni račun. Predikati in kvantifikatorji. Interpretacija. Logično veljavne izjavne formule ter enakovredne izjavne formule.

Relacije in urejenosti. Dvomestne relacije in njihove lastnosti. Operacije na relacijah. Inverzna relacija. Produkt in potence relacij. Ovojnice. Ekvivalenčna relacija. Delna urejenost, linearna urejenost.

Osnove teorije grafov: stopnja, regularnost, podgraf, nekatere družine grafov, dvodelnost, grafovske matrike. Drevesa. Eulerjevi in Hamiltonovi sprehodi obhodi in cikli. Ravninski grafi. Barvanja grafov.

1. M. Juvan, P. Potočnik: Teorija grafov in kombinatorika : primeri in rešene naloge, 2. natis, Ljubljana: DMFA-založništvo, 2007.
2. N. Prijatelj: Osnove matematične logike. Del 1, Simbolizacija, Ljubljana : Društvo matematikov, fizikov in astronomov, 1982, 1992.
3. N. Prijatelj: Osnove matematične logike. Del 2, Formalizacija, Ljubljana : Društvo matematikov, fizikov in astronomov Slovenije, 1992.
4. N. Prijatelj: Matematične strukture. 1, Množice, relacije, funkcije, 5. izd. - Ljubljana : Društvo matematikov, fizikov in astronomov Slovenije, 1996.
5. D. Veljan: Kombinatorna i diskretna matematika, Zagreb : Algoritam, 2001.
6. R. J. Wilson, J. J. Watkins: Uvod v teorijo grafov, Ljubljana: Društvo matematikov, fizikov in astronomov Slovenije, 1997.

Študent spozna pojem matematičnega dokaza in pravilnega sklepanja, osnovne diskretne strukture ter osnove teorije grafov.

Znanje in razumevanje: Poznavanje osnovnih pojmov iz logike, urejenostnih struktur in iz teorije grafov ter razumevanje osnovnih povezav med njimi.
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ž, PAK, Igor. Triangulations of Cayley and Tutte polytopes. Advances in mathematics, ISSN 0001-8708, 2013, vol. 245, str. 1-33. [COBISS-SI-ID 16706905]
KONVALINKA, Matjaž. The role of residue and quotient tables in the theory of k-Schur functions. Journal of combinatorial theory. Series A, ISSN 0097-3165, 2015, vol. 136, str. 1-38. [COBISS-SI-ID 17339993]

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. http://dx.doi.org/10.1007/s10801-011-0340-2. [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]

Riste Škrekovski:
KAISER, Tomáš, ŠKREKOVSKI, Riste. T-joins intersecting small edge-cuts in graphs. Journal of graph theory, ISSN 0364-9024, 2007, vol. 56, no. 1, str. 64-71. [COBISS-SI-ID 14373977]
DVOŘÁK, Zdeněk, ŠKREKOVSKI, Riste. A theorem about a contractible and light edge. SIAM journal on discrete mathematics, ISSN 0895-4801, 2006, vol. 20, no. 1, str. 55-61. [COBISS-SI-ID 14249305]
JUNGIĆ, Veselin, KRÁL', Daniel, ŠKREKOVSKI, Riste. Colorings of plane graphs with no rainbow faces. Combinatorica, ISSN 0209-9683, 2006, vol. 26, no. 2, str. 169-182. [COBISS-SI-ID 13954393]