Teorija grafov

2022/2023
Program:
Magistrski študijski program 2. stopnje Matematika
Letnik:
1 ali 2 letnik
Semester:
prvi ali drugi
Vrsta:
temeljni izbirni
Skupina:
M2
ECTS:
6
Jezik:
slovenski, angleški
Ure na teden – 1. ali 2. semester:
Predavanja
3
Seminar
0
Vaje
2
Laboratorij
0
Vsebina

Prirejanja in faktorji (min-max izreki, neodvisne množice in pokritja, Tuttov izrek o 1-faktorju)
Povezanost (struktura 2-povezanih in k-povezanih grafov, dokaz in uporabe Mengerjevih izrekov)
Barvanja grafov (meje, dokaz Brooksovega izreka, struktura k-kromatičnih grafov, Turanov izrek, kromatični polinom, tetivni grafi)
Ravninski grafi (dualni graf, izrek Kuratowskega, konveksne vložiitve, barvanja ravninskih grafov, prekrižno število)
Predavatelj izbere še eno izmed naslednjih tem: barvanja povezav in graf povezav, hamiltonski grafi, popolni grafi, ekstremalni problemi, dominacija v grafih, simetrijske lastnosti grafov II.

Temeljni literatura in viri

R. Diestel: Graph Theory, 3. izdaja, Springer, Berlin, 2005.
A. Bondy, U.S.R. Murty: Graph Theory, 2. izdaja, Springer, Berlin, 2008.
D. West: Introduction to Graph Theory, 2. izdaja, Prentice Hall, Upper Saddle River, 2005.
R. J. Wilson, M. Watkins: Uvod v teorijo grafov, DMFA Slovenije, Ljubljana, 1997.

Cilji in kompetence

Študent poglobi in razširi znanje teorije grafov. Spozna uporabnost grafov in omrežij na različnih področjih matematike ter možnosti za njihovo uporabo tudi v drugih vejah znanosti.

Predvideni študijski rezultati

Znanje in razumevanje: Slušatelj poglobi znanje iz teorije grafov.
Uporaba: Grafi omogočajo matematično modeliranje različnih pojavov. Slušatelj se seznani z vrsto matematičnih rezultatov, ki opisujejo lastnosti grafov in tako omogočajo matematično analizo modelov, opisanih z grafi.
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 grafi.
Prenosljive spretnosti – niso vezane le na en predmet: Sposobnost opisa problemov iz vsakdanjega življenja s pomočjo matematičnih struktur, še posebej z grafi. Sposobnost uporabe matematičnih orodij za reševanje problemov.

Metode poučevanja in učenja

predavanja, vaje, domače naloge, konzultacije

Načini ocenjevanja

Izpit iz vaj (pisni izpit)
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]