Teorija grafova

Prijava

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 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	0 %	20 %	0 %	0 %
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.