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.

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

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

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

Jednom tjedno.

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

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.