Metrična teorija grafov

Cilji in predmetno specifične kompetence

Izobraževalni cilj je študentu predstaviti poglobljen vpogled v aktualne trende v metrični teoriji grafov, kar lahko služi kot uvod v raziskovalno delo, ter hkrati razvijati sposobnosti študenta za samostojno reševanje problemov in razumevanje zahtevnih matematičnih konceptov. Študijski rezultat je poglobljeno poznavanje aktualnih področij metrične teorije grafov, orodij za njeno proučevanje ter poglobljeno razumevanje nekaterih specialnih pojmov iz teorije metričnih prostorov nad grafi.

Opis vsebine

• Osnovni koncepti (različne metrike, izometrije,...).
• Konveksnost (različne konveksnosti, produkti in metrične škatle,...).
• Metrično definirani razredi grafov (medianski grafi, delne kocke, delni Hammingovi grafi..., ter njihove lastnosti).
• Algoritmični vidiki.
• Kanonična metrična reprezentacija.
• Uporaba metričnih konceptov (dokaz enolične faktorizacije preko metričnih škatel, uporabe v kemijski teoriji grafov, teorija medijev,...).

Nekatere izmed teh tem so obdelane podrobneje, druge pa le na osnovni ravni. Pri izboru se upoštevajo interesi in raziskovalne usmeritve študentov. Spodaj navedena literatura praviloma služi le kot osnova in je nadgrajena z bolj specializiranimi teksti.

Temeljna literatura

• M. Aigner: Discrete Mathematics, American Mathematical Society, Providence, 2007.
• D. Eppstein, J.-C. Falmagne, S. Ovchinnikov: Media Theory, Springer, Berlin, 2008.
• P. Hell, J. Nešetril: Graphs and Homomorphisms, Oxford University Press, Oxford, 2004. 
• W. Imrich, S. Klavžar: Product Graphs: Structure and Recognition, Wiley-Interscience, New York, 2000. 
• D. B. West: Introduction to Graph Theory, 2. izdaja, Prentice Hall, Upper Saddle River, 2001.
  

Predvideni študijski dosežki

/

Metode poučevanja in učenja

Predavanja, seminarji in projektno delo.

Pogoji za vključitev v delo oziroma za opravljanje študijskih obveznosti

Splošni pogoji za vpis na doktorski študij.

Metode ocenjevanja in ocenjevalna lestvica

• domače naloge in projekti
• ocene: 1-5 (negativno), 6-10 (pozitivno) (po Statutu UL)

Metode evalvacije kakovosti

Študentska anketa (univerzitetna in interna), samoevalvacija.

Sestavljalec učnega načrta

prof. dr. Sandi Klavžar

Izvajalci

• prof. dr. Sandi Klavžar
• doc. dr. Riste Škrekovski