Diskretne strukture 2

2022/2023
Program:
Interdisciplinarni univerzitetni študijski program 1. stopnje Računalništvo in matematika
Letnik:
1 letnik
Semester:
drugi
Vrsta:
obvezni
ECTS:
6
Jezik:
slovenski
Ure na teden – 2. semester:
Predavanja
3
Seminar
0
Vaje
3
Laboratorij
0
Vsebina

Osnovno o grafih. Drevesa. Eulerjevi in Hamiltonovi grafi. Usmerjeni grafi in turnirji. Povezanost in ravninskost grafov. Barvanje vozlišč in povezav grafa. Osnove algebre: grupe, kolobarji, polinomi, komutativni obsegi.

Temeljni literatura in viri

Gašper Fijavž: Diskretne strukture, Fakulteta za računalništvo in informatiko (2015) [elektronski vir], http://matematika.fri.uni-lj.si/ds/ds.pdf
Riste Škrekovski: Diskretne strukture II [Elektronski vir] : zapiski predavanj, http://www.fmf.uni-lj.si/skreko/Gradiva/DS2-skripta.pdf , ISBN 978-961-92887-3-3, 62 str.
I. N. Herstein, Abstract Algebra, Wiley and sons (1999).
Martin Juvan in Primož Potočnik: Teorija grafov in kombinatorika: primeri in rešene naloge, Društvo matematikov, fizikov in astronomov Slovenije, Ljubljana 2000, ISBN: 961-212-105-2, 173 str.

Cilji in kompetence

Pri Diskretnih strukturah 2 študent osvoji zahtevnejše vsebine iz teorije grafov in se spozna z osnovami abstraktne algebre.

Predvideni študijski rezultati

Znanje in razumevanje: Predmet temelji na znanju, pridobljenem pri Diskretnih strukturah 1. Vsebine predmeta Diskretne strukture 2 so del potrebnega predznanja za predmete Teorija kodiranja in kriptografija, Kombinatorika ter Optimizacijske metode.
Uporaba: Teorija grafov je uporabna v teoriji algoritmov kot orodje za modeliranje raznih problemov. Algebrske strukture se uporabljajo v kriptografiji in kodiranju.
Refleksija: Študentje spoznajo razliko med zvezno in diskretno matematiko.
Prenosljive spretnosti - niso vezane le na en predmet: Modeliranje problemov in omrežnih struktur z grafi in drevesi. Obvladanje osnovnih algebrskih struktur.

Metode poučevanja in učenja

Predavanja in vaje, domače naloge.

Načini ocenjevanja

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

Reference nosilca

Primož Potočnik:
POTOČNIK, Primož. Tetravalent arc-transitive locally-Klein graphs with long consistent cycles. European journal of combinatorics, ISSN 0195-6698, 2014, vol. 36, str. 270-281. [COBISS-SI-ID 16862041]
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ž. Edge-colourings of cubic graphs admitting a solvable vertex-transitive group of automorphisms. Journal of combinatorial theory. Series B, ISSN 0095-8956, 2004, vol. 91, no. 2, str. 289-300. [COBISS-SI-ID 13087321]
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]
Sandi Klavžar:
BREŠAR, Boštjan, HENNING, Michael A., KLAVŽAR, Sandi, RALL, Douglas F. Domination games played on graphs. Cham: Springer Nature, cop. 2021. X, 122 str. [COBISS-SI-ID 60317443]
KLAVŽAR, Sandi, MOLLARD, Michel. Daisy cubes and distance cube polynomial. European journal of combinatorics. Aug. 2019, vol. 80, str. 214-223. [COBISS-SI-ID 18659161]
HENNING, Michael A., KLAVŽAR, Sandi, RALL, Douglas F. The 4/5 upper bound on the game total domination number. Combinatorica. 2017, vol. 37, iss. 2, str. 223-251. [COBISS-SI-ID 18018137]
BUJTÁS, Csilla, KLAVŽAR, Sandi. Improved upper bounds on the domination number of graphs with minimum degree at least five. Graphs and combinatorics. 2016, vol. 32, iss. 2, str. 511-519. [COBISS-SI-ID 17630041]
KLAVŽAR, Sandi. Structure of Fibonacci cubes: a survey. Journal of combinatorial optimization. 2013, vol. 25, iss. 4, str. 505-522. [COBISS-SI-ID 16603737]
BREŠAR, Boštjan, KLAVŽAR, Sandi, RALL, Douglas F. Domination game and an imagination strategy. SIAM journal on discrete mathematics. 2010, vol. 24, no. 3, str. 979-991. [COBISS-SI-ID 15648089]