Teorija grafov

2021/2022
Program:
Interdisciplinarni magistrski študijski program 2. stopnje Računalništvo in matematika
Letnik:
1 ali 2 letnik
Semester:
prvi ali drugi
Vrsta:
temeljni izbirni
Skupina:
B
ECTS:
6
Jezik:
slovenski, angleški
Ure na teden – 1. ali 2. semester:
Predavanja
3
Seminar
0
Vaje
2
Laboratorij
0
Vsebina

Povezanost, struktura 3-povezanih grafov. Ravninski grafi, dokaz izreka Kuratowskega, Schnyderjev izrek.
Spektralna teorija grafov.
Barvanja in pretoki.
Prirejanja in pokritja v grafih, Tuttov izrek.
Metrična teorija grafov, vložitve metričnih prostorov v grafe.
Operacije nad grafi, grafovski produkti.

Temeljni literatura in viri
  • A. Bondy, U.S.R. Murty: Graph Theory, 2. izdaja, Springer, Berlin, 2008.
  • R. Diestel: Graph Theory, 3rd Edition, Springer, Berlin, 2005.- W. Imrich, S. Klavžar, D.F. Rall, Topics in Graph Theory, A K Peters, Wellesley, 2008.- M. Juvan, P. Potočnik: Teorija grafov in kombinatorika: primeri in rešene naloge, Društvo matematikov, fizikov in astronomov Slovenije, Ljubljana 2000, 173 str. - D.B. West, Introduction to Graph Theory, 2nd Edition, Prentice Hall, Upper Sadle River, 2001.
Cilji in kompetence

Študent poglobi in razširi znanje teorije grafov. Spozna uporabnost grafov in omrežij na različnih področjih matematike (kombinatorika, linearna algebra, teorija grup, delno urejene množice ...) ter možnosti za njihovo uporabo tudi v drugih vejah znanosti.

Predvideni študijski rezultati

Znanje in razumevanje:
Študent natančneje spozna izbrana področja teorije grafov. Seznani se z najnovejšimi rezultati tega področja in z njegovimi uporabami v matematiki in drugih področjih znanosti.

Metode poučevanja in učenja

Predavanja, vaje, domače naloge, konzultacije, projekti.

Načini ocenjevanja

Sprotno preverjanje (domače naloge, kolokviji in projektno delo).
Končno preverjanje (pisni in ustni izpit).
(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]
Sandi Klavžar:
KLAVŽAR, Sandi, SHPECTOROV, Sergey. Convex excess in partial cubes. Journal of graph theory, ISSN 0364-9024, 2012, vol. 69, no. 4, str. 356-369. [COBISS-SI-ID 16243033]
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]
KLAVŽAR, Sandi. On the canonical metric representation, average distance, and partial Hamming graphs. European journal of combinatorics, ISSN 0195-6698, 2006, vol. 27, no. 1, str. 68-73. [COBISS-SI-ID 13858905]
Riste Škrekovski:
GOVORČIN, Jelena, KNOR, Martin, ŠKREKOVSKI, Riste. Line graph operation and small worlds. Information processing letters, ISSN 0020-0190. [Print ed.], 2013, vol. 113, iss. 5-6, str. 196-200. [COBISS-SI-ID 16561497]
DVOŘÁK, Zdeněk, LIDICKÝ, Bernard, ŠKREKOVSKI, Riste. Randić index and the diameter of a graph. European journal of combinatorics, ISSN 0195-6698, 2011, vol. 32, iss. 3, str. 434-442. [COBISS-SI-ID 17410905]
KAISER, Tomáš, STEHLÍK, Matěj, ŠKREKOVSKI, Riste. On the 2-resonance of fullerenes. SIAM journal on discrete mathematics, ISSN 0895-4801, 2011, vol. 25, no. 4, str. 1737-1745. [COBISS-SI-ID 16244569]
Arjana Žitnik:
MILANIČ, Martin, PISANSKI, Tomaž, ŽITNIK, Arjana. Dilation coefficient, plane-width, and resolution coefficient of graphs. Monatshefte für Mathematik, ISSN 0026-9255, 2013, vol. 170, no. 2, str. 179-193. [COBISS-SI-ID 1024499540]
ŽITNIK, Arjana, HORVAT, Boris, PISANSKI, Tomaž. All generalized Petersen graphs are unit-distance graphs. Journal of the Korean Mathematical Society, ISSN 0304-9914, 2012, vol. 49, no. 3, str. 475-491. [COBISS-SI-ID 16217945]
JURIŠIĆ, Aleksandar, TERWILLIGER, Paul, ŽITNIK, Arjana. The Q-polynomial idempotents of a distance-regular graph. Journal of combinatorial theory. Series B, ISSN 0095-8956, 2010, vol. 100, iss. 6, str. 683-690. [COBISS-SI-ID 15688537]