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
- modelirati probleme pomoću grafova
- dokazivati činjenice o strukturi grafova
- razumjeti i kreirati algoritme na grafovima
- razlikovati vrijednosti teoretskog i algoritamskog rješenja zadanog problema
- dokazivati algoritme na grafovima
- razumjeti pročitati složenije članke iz teorije grafova
Oblici nastave
Predavanja
Predavanja uključuju i rasprave o rješavanju zadataka.
Provjere znanjaTijekom tjedana bez nastave koji su rezervirani za međuispit i završni ispit.
KonzultacijeJednom tjedno.
Programske vježbeizrađ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
- Pojam grafa. Repetitorij temeljnih pojmova. Glavni primjeri.
- Faktorizacije grafova. 1-faktori. Turniri.
- Planarnost. Eulerova formula. Teorem Kuratowskog.
- Grafovi na drugim plohama. Dualni grafovi. Beskonačni grafovi.
- Algoritmi za ispitivanje planarnosti.
- Ramseyeva teorija.
- Bojanje vrhova grafa. Brooksov teorem. Bojanje karata.
- Bojanje bridova. Kromatski polinomi.
- Usmjereni grafovi. Usmjerivost. Eulerovski digrafovi. Kritični put.
- Turniri digrafova. Diskretni Markovljevi lanci.
- Sparivanja. Ženidbeni problem.
- Teorija transverzala. Primjena na latinske kvadrate. Mengerov teorem.
- Transportne mreže. Maksimalni protok. Algoritmi za nalaženje maksimalnog protoka.
- Slučajni grafovi. Jednostavna svojstva gotovo svih grafova.
- 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
D. Veljan (2001.), Kombinatorna i diskretna matematika, Algoritam
Nositelji
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