CILJ KOLEGIJA:
Razumijevanje temeljnih pojmova, teorema i algoritama iz teorije grafova,te rješavanje vezanih problema.
NASTAVNI SADRŽAJI:
- Vršna i bridna povezanost, 2-povezanost, Maderov teorem, Mengerov teorem, Ford-Fulkersonov algoritam
- Sparivanja (matchings), Hallov teorem, Kőnigov teorem, Tutteov uvjet, algoritam za minimalno sparivanje u bipartitnom grafu
- Bojenja grafova, pohlepna bojenja, Brooksov teorem, Teorem o 5 boja, Gallai-Royev teorem, Vizingov teorem
- Teorem o matricama i stablima (matrix-tree theorem), Cauchy-Binetova formula
- Algebarske metode, svojstvene vrijednosti grafova, jako regularni grafovi, PageRank algoritam
- Vjerojatnosna metoda i Ramseyeva teorija
- Ekstremalna teorija grafova: Turánov teorem, Kővári-Sós-Turánov teorem
|
Pristupačnost
