Teorija grafova

Opis predmeta

Prikazuju se glavni problemi teorije grafova i usmjerenih grafova, te daju njihova teoretska i algoritamska rješenja. Oni uključuju probleme faktorizacije grafova, problem planarnosti, sparivanja, problem nalaženja maksimalnog toka, usmjerivosti, kao i probleme obojivosti. Dat će se uvod u teoriju slučajnih grafova.

Opće kompetencije

Modeliranje pomoću diskretnih matematičkih struktura, posebice pomoću grafova, te rješavanje tako izmodeliranih problema. Razvijanje tehnika promišljanja i dokazivanja tvrdnji i tehnika kreiranja, analiziranja, testiranja i dokazivanja algoritama na grafovima.

Ishodi učenja

  1. modelirati probleme pomoću grafova
  2. dokazivati činjenice o strukturi grafova
  3. razumjeti i kreirati algoritme na grafovima
  4. razlikovati vrijednosti teoretskog i algoritamskog rješenja zadanog problema
  5. dokazivati algoritme na grafovima
  6. razumjeti pročitati složenije članke iz teorije grafova

Oblici nastave

Predavanja

Predavanja uključuju i rasprave o rješavanju zadataka.

Provjere znanja

Tijekom tjedana bez nastave koji su rezervirani za međuispit i završni ispit.

Konzultacije

Jednom tjedno.

Programske vježbe

izrađivat će se individualno kod kuće.

Način ocjenjivanja

Kontinuirana nastava Ispitni rok
Vrsta provjere Prag Udio u ocjeni Prag Udio u ocjeni
Domaće zadaće 10 % 20 % 10 % 20 %
Međuispit: Pismeni 0 % 40 % 0 %
Završni ispit: Pismeni 0 % 40 %
Ispit: Pismeni 0 % 100 %

Tjedni plan nastave

  1. Pojam grafa. Repetitorij temeljnih pojmova. Glavni primjeri.
  2. Faktorizacije grafova. 1-faktori. Turniri.
  3. Planarnost. Eulerova formula. Teorem Kuratowskog.
  4. Grafovi na drugim plohama. Dualni grafovi. Beskonačni grafovi.
  5. Algoritmi za ispitivanje planarnosti.
  6. Ramseyeva teorija.
  7. Bojanje vrhova grafa. Brooksov teorem. Bojanje karata.
  8. Bojanje bridova. Kromatski polinomi.
  9. Usmjereni grafovi. Usmjerivost. Eulerovski digrafovi. Kritični put.
  10. Turniri digrafova. Diskretni Markovljevi lanci.
  11. Sparivanja. Ženidbeni problem.
  12. Teorija transverzala. Primjena na latinske kvadrate. Mengerov teorem.
  13. Transportne mreže. Maksimalni protok. Algoritmi za nalaženje maksimalnog protoka.
  14. Slučajni grafovi. Jednostavna svojstva gotovo svih grafova.
  15. Završni ispit i usmena predaja praktičnih zadataka na računalu.

Studijski programi

Sveučilišni diplomski
[FER2-HR] Automatika - profil
Predmeti matematike, fizike i prirodoslovlja (2. semestar)
[FER2-HR] Bežične komunikacijske tehnologije - profil
Predmeti matematike, fizike i prirodoslovlja (2. semestar)
[FER2-HR] Elektroenergetika - profil
Predmeti matematike, fizike i prirodoslovlja (2. semestar)
[FER2-HR] Elektroničko i računalno inženjerstvo - profil
Predmeti matematike, fizike i prirodoslovlja (2. semestar)
[FER2-HR] Elektronika - profil
Predmeti matematike, fizike i prirodoslovlja (2. semestar)
[FER2-HR] Elektrotehnički sustavi i tehnologija - profil
Predmeti matematike, fizike i prirodoslovlja (2. semestar)
[FER2-HR] Obradba informacija - profil
Predmeti matematike, fizike i prirodoslovlja (2. semestar)
[FER2-HR] Programsko inženjerstvo i informacijski sustavi - profil
Predmeti matematike, fizike i prirodoslovlja (2. semestar)
[FER2-HR] Računalno inženjerstvo - profil
Predmeti matematike, fizike i prirodoslovlja (2. semestar)
[FER2-HR] Računarska znanost - profil
Predmeti matematike, fizike i prirodoslovlja (2. semestar)
[FER2-HR] Telekomunikacije i informatika - profil
Predmeti matematike, fizike i prirodoslovlja (2. semestar)

Literatura

R. J. Wilson (1999.), Introduction to Graph Theory, Pearson Education Ltd.
D. Veljan (2001.), Kombinatorna i diskretna matematika, Algoritam
B. Bollobas (1998.), Modern Graph Theory, Springer
W. D. Wallis (2000.), A Beginners Guide to Graph Theory, Birkhäuser
G. Chartrand and L. Lesniak (2005.), Graphs and Digraphs, Chapman & Hall / CRC

Nositelji

Prof. dr. sc.
Mario Osvin Pavčević

Za studente

Izvedba

ID 34560
  Ljetni semestar
4 ECTS
R0 Engleski jezik
R1 E-učenje
45 Predavanja
0 Seminar
0 Auditorne vježbe
0 Laboratorijske vježbe
0 Konstrukcijske vježbe

Ocjenjivanje

85 izvrstan
70 vrlo dobar
55 dobar
45 dovoljan

Sličan predmet