Cilji in kompetence
Cilji predmeta so, da študenti osvojijo osnovne pojme teorije grafov, razumejo probleme reševanja v kombinatorični optimizaciji, poznajo klasične kombinatorične optimizacijske probleme in postopke za iskanje rešitev, znajo izvajati korake obravnavanih algoritmov in uporabljati programsko orodja ter pridobijo spretnosti modeliranja določenih praktičnih problemov s pomočjo teorije grafov.
Vsebina
Osnove teorije grafov
grafi, usmerjeni grafi, uteženi grafi, omrežja, primeri uporabe grafov in digrafov, izomorfni grafi, posebni primeri grafov, karte grafov, povezanost, ravninskost, matrika sosednosti in incidenčna matrika, drevesa, vpeta drevesa, sprehodi in obhodi v grafih, Eulerjevi in Hamiltonovi grafi, Eulerjev obhod, Hamiltonov cikel, barvanje vozlišč in povezav grafov, totalno barvanje, kromatično število in kromatični indeks grafa.
Kombinatorična optimizacija
algoritmi, učinkovitost algoritmov, pregledovanje grafov, iskanje v globino in v širino, DFS in BFS drevo, iskanje najkrajših ter najdaljših poti, Dijkstra algoritem, optimizacija projekta, iskanje minimalnega vpetega drevesa, Primov algoritem, problemi Eulerjevega in Hamiltonovega tipa, Fleury-jev algoritem, kitajski problem poštarja, problem trgovskega potnika, požrešni algoritem, uporaba barvanja grafov v primerih iz prakse (načrtovanje urnikov, prometnih tokov, skladiščenja), use computer software.
Metode poučevanja in učenja
Predavanja, diskusija in računalniške vaje.
Predvideni študijski rezultati - znanje in razumevanje
Znanje in razumevanje:
Po zaključku tega predmeta bo študent sposoben:
- razložiti osnovne pojme teorije grafov in probleme reševanja v kombinatorični optimizaciji,
- prepoznati in analizirati klasične kombinatorične optimizacijske probleme,
- izvesti obravnavane algoritme po korakih in uporabljati programska orodja,
- poiskati najkrajšo in najdaljšo pot v grafih in digrafih,
- določiti minimalno vpeto drevo,
- poiskati Eulerjev obhod in določiti meje za Hamiltonov cikel,
- s požrešnim algoritmom dobro pobarvati graf ter določiti meje za kromatično število in kromatični indeks grafa,
- modelirati in rešiti nekatere praktične probleme s pomočjo teorije grafov.
Predvideni študijski rezultati - Prenosljive/ključne spretnosti in drugi atributi
Modeliranje določenih problemov s področja prometa z uporabo teorije grafov ter iskanje rešitev le teh na podlagi obravnavanih algoritmov.
Temeljni literatura in viri
R. J. Wilson, J. J. Watkins, Uvod v teorijo grafov, DMFA Slovenije, Ljubljana, 1997.
J. Žerovnik, Osnove teorije grafov in diskretne optimzacije, 2. popravljena izdaja, FS UM, Maribor, 2005.
J. M. Aldous, R. J. Wilson, Graphs and applications: an Introductory approach, Springer, 5th printing, London, 2006.
L. R: Foulds, Graph theory Application, Springer, New York, 1992.
F. S. Hillier, G. J. Lieberman, Introduction to Operation Research, Ninth Edition, McGraw-Hill, New York, 2009.
Pogoji za vključitev v delo oz. za opravljanje študijskih obveznosti
Ni pogojev za vključitev v delo.
Pogoji za opravljanje študijskih obveznosti: pogoj za pristop k ustnemu izpitu je opravljen pisni izpit z vsaj 60% in pozitivno ocenjena individualna domača naloga.
Podrobnosti o izvedbi in ocenjevanju Opomba: pogoj za pristop k ustnemu izpitu je opravljen pisni izpit z vsaj 60% in pozitivno ocenjena individualna domača naloga.
