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:

ECTS:

Jezik:

slovenski, angleški

Nosilec predmeta:

prof. dr. Sandi Klavžar, prof. dr. Primož Potočnik, prof. dr. Riste Škrekovski, izr. prof. dr. Arjana Žitnik

Ure na teden – 1. ali 2. semester:

Predavanja

Seminar

Vaje

Laboratorij

Pogojev za vključitev v delo ni.

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.

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.

Š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.

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.

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

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)

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]