MPŠ
MPŠ MP&Scaron MP&Scaron MP&Scaron Avtorji

Mednarodna
podiplomska šola
Jožefa Stefana

Jamova 39
SI-1000 Ljubljana
Slovenija

Tel: (01) 477 31 00
Faks: (01) 477 31 10
E-pošta: info@mps.si

Išči

Opis predmeta

Izbrana poglavja iz diskretne matematike

Programi:

Informacijske in komunikacijske tehnologije, 2. stopnja

Sodelavci:

prof. dr. Sandi Klavžar

Cilji:

Študenta seznaniti z nekaterimi aktualnimi področji diskretne uporabne matematike, ki so bodisi že našla uporabo, ali pa predstavljajo potencial za uporabe v informacijsko-komunikacijskih tehnologijah.

Vsebina:

1) Produkti grafov
Osnovne lastnosti. Nekatere invariante na produktih (povezanost, dominacija).

2) Modeli povezovalnih omrežij
Hiperkocke in njihove inačice. Mrežni in torusni grafi. Delne kocke, Hammingovi grafi in njihove uporabe. Fibonaccijeve kocke.

3) Teorija kodiranja
Linearne kode. Kode v grafih. 1-popolne kode v grafih. r-popolne kode v torusnih grafih.

4) Barvanje grafov
Problem dodeljevanja frekvenc. L(2,1)-barvanje in posplošitve.

Temeljna literatura in viri:

• Biggs, Norman L. Discrete mathematics. Second edition. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1989.
• Gross, Jonathan L.; Yellen, Jay Graph theory and its applications. Second edition. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2006.
• Imrich, W., Klavžar, S. Product graphs: structure and recognition, (Wiley-Intersciences series in discrete mathematics and optimization). New York [etc.]: J. Wiley & Sons, cop. 2000.
• Ling, San; Xing, Chaoping Coding theory. A first course. Cambridge University Press, Cambridge, 2004.
• Matoušek, J.; Nešetril, J. Invitation to discrete mathematics. The Clarendon Press, Oxford University Press, New York, 1998.

Izbrane reference nosilca:

• KLAVŽAR, Sandi, PETERIN, Iztok, YERO, Ismael G. Graphs that are simultaneously efficient open domination and efficient closed domination graphs. Discrete applied mathematics, ISSN 0166-218X. [Print ed.], 2017, vol. 217, iss. 3, str. 613-621. http://dx.doi.org/10.1016/j.dam.2016.09.027. [COBISS.SI-ID 17827673], [JCR, SNIP, Scopus do 17. 12. 2016: št. citatov (TC): 0, čistih citatov (CI): 0]
• KLAVŽAR, Sandi, KOŠMRLJ, Gašper, SCHMIDT, Simon. On graphs with small game domination number. Applicable analysis and discrete mathematics, ISSN 1452-8630, 2016, vol. 10, no. 1, str. 30-45. http://dx.doi.org/10.2298/AADM160207003K. [COBISS.SI-ID 17666137], [JCR, SNIP, WoS do 1. 11. 2016: št. citatov (TC): 1, čistih citatov (CI): 0, Scopus do 30. 11. 2016: št. citatov (TC): 1, čistih citatov (CI): 0]
• KLAVŽAR, Sandi, RHO, Yoomi. On the Wiener index of generalized Fibonacci cubes and Lucas cubes. Discrete applied mathematics, ISSN 0166-218X. [Print ed.], 2015, vol. 187, str. 155-160. http://dx.doi.org/10.1016/j.dam.2015.02.002. [COBISS.SI-ID 17295961], [JCR, SNIP, WoS do 25. 12. 2016: št. citatov (TC): 4, čistih citatov (CI): 3, Scopus do 28. 11. 2016: št. citatov (TC): 5, čistih citatov (CI): 3]
• KLAVŽAR, Sandi, SHAO, Zehui. Local colorings of Cartesian product graphs. International journal of computer mathematics, ISSN 0020-7160, 2015, vol. 92, no. 4, str. 694-699. http://dx.doi.org/10.1080/00207160.2014.918609. [COBISS.SI-ID 17225049], [JCR, SNIP, WoS do 20. 2. 2015: št. citatov (TC): 0, čistih citatov (CI): 0, Scopus do 20. 2. 2015: št. citatov (TC): 0, čistih citatov (CI): 0]
• KLAVŽAR, Sandi, MOLLARD, Michel. Asymptotic properties of Fibonacci cubes and Lucas cubes. Annals of combinatorics, ISSN 0218-0006, 2014, vol. 18, no. 3, str. 447-457. http://dx.doi.org/10.1007/s00026-014-0233-x. [COBISS.SI-ID 17087065], [JCR, SNIP, WoS do 27. 11. 2016: št. citatov (TC): 5, čistih citatov (CI): 1, Scopus do 27. 11. 2016: št. citatov (TC): 5, čistih citatov (CI): 1]
• KLAVŽAR, Sandi, NADJAFI-ARANI, M. J. Computing distance moments on graphs with transitive Djoković-Winkler relation. Discrete applied mathematics, ISSN 0166-218X. [Print ed.], 2014, vol. 166, str. 269-272. http://dx.doi.org/10.1016/j.dam.2013.10.006. [COBISS.SI-ID 16893273], [JCR, SNIP, WoS do 2. 5. 2015: št. citatov (TC): 1, čistih citatov (CI): 1, Scopus do 14. 10. 2015: št. citatov (TC): 1, čistih citatov (CI): 0]
• KLAVŽAR, Sandi, RHO, Yoomi. Fibonacci (p,r)-cubes as Cartesian products. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2014, vol. 328, str. 23-26. http://dx.doi.org/10.1016/j.disc.2014.03.027. [COBISS.SI-ID 16970585], [JCR, SNIP, WoS do 30. 6. 2014: št. citatov (TC): 0, čistih citatov (CI): 0, Scopus do 7. 9. 2015: št. citatov (TC): 0, čistih citatov (CI): 0]
• KLAVŽAR, Sandi, NADJAFI-ARANI, M. J. On the difference between the revised Szeged index and the Wiener index. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2014, vol. 333, str. 28-34. http://dx.doi.org/10.1016/j.disc.2014.06.006. [COBISS.SI-ID 17065817], [JCR, SNIP, WoS do 3. 7. 2016: št. citatov (TC): 2, čistih citatov (CI): 2, Scopus do 28. 12. 2016: št. citatov (TC): 3, čistih citatov (CI): 3]
• KLAVŽAR, Sandi, NADJAFI-ARANI, M. J. Wiener index in weighted graphs via unification of [Theta] [sup] [ast]-classes. European journal of combinatorics, ISSN 0195-6698, 2014, vol. 36, str. 71-76. http://dx.doi.org/10.1016/j.ejc.2013.04.008. [COBISS.SI-ID 16768089], [JCR, SNIP, WoS do 25. 12. 2016: št. citatov (TC): 12, čistih citatov (CI): 8, Scopus do 17. 11. 2016: št. citatov (TC): 10, čistih citatov (CI): 5]
• KLAVŽAR, Sandi, NADJAFI-ARANI, M. J. Improved bounds on the difference between the Szeged index and the Wiener index of graphs. European journal of combinatorics, ISSN 0195-6698, 2014, vol. 39, str. 148-156. http://dx.doi.org/10.1016/j.ejc.2014.01.005. [COBISS.SI-ID 16861017], [JCR, SNIP, WoS do 3. 7. 2016: št. citatov (TC): 6, čistih citatov (CI): 5, Scopus do 28. 12. 2016: št. citatov (TC): 7, čistih citatov (CI): 6]
• KLAVŽAR, Sandi, MA, Meijie. The domination number of exchanged hypercubes. Information processing letters, ISSN 0020-0190. [Print ed.], 2014, vol. 114, iss. 4, str. 159-162. http://dx.doi.org/10.1016/j.ipl.2013.12.005. [COBISS.SI-ID 16819289], [JCR, SNIP, WoS do 3. 6. 2016: št. citatov (TC): 5, čistih citatov (CI): 4, Scopus do 27. 11. 2016: št. citatov (TC): 9, čistih citatov (CI): 8]
• KLAVŽAR, Sandi, MA, Meijie. Average distance, surface area, and other structural properties of exchanged hypercubes. The journal of supercomputing, ISSN 0920-8542, 2014, vol. 69, no. 1, str. 306-317. http://dx.doi.org/10.1007/s11227-014-1153-6. [COBISS.SI-ID 17064793], [JCR, SNIP, WoS do 3. 2. 2016: št. citatov (TC): 2, čistih citatov (CI): 2, Scopus do 3. 5. 2016: št. citatov (TC): 2, čistih citatov (CI): 2]

Načini preverjanja znanja:

Seminar (20%)
Ustni izpit (80%)

Obveznosti študentov:

Seminar in ustni izpit.

Zunanje povezave: