Teorija grafova

Repozitorij

Repozitorij je prazan

Anketa

Na ovoj stranici trenutno nije odabrana niti jedna anketa!

Teorija grafova

Šifra: 284244
ECTS: 5.0
Nositelji: izv. prof. Nina Kamčev
Prijava ispita: Studomat
Opterećenje:

1. komponenta

Vrsta nastaveUkupno
Predavanja 45
* Opterećenje je izraženo u školskim satima (1 školski sat = 45 minuta)
Opis predmeta:
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
Literatura:
  1. Graph Theory, 3rd ed. https://diestel-graph-theory.com/basic.html, Reinhard Diestel, Berlin; Heidelberg: Springer-Verlag, 2005.
  2. Graph Theory, bilješke sa Sveučilišta u Cambridgeu. ( https://ak2316.user.srcf.net/files/ii-graph-theory/graph-theory.pdf ), Julian Sahasrabudhe.
1. semestar
Ostali izborni predmeti - Redovni Studij - Računarstvo i matematika

2. semestar Ne predaje se
Ostali izborni predmeti - Redovni Studij - Računarstvo i matematika

3. semestar
Izborni predmet 3, 4, 5, 6 - Redovni Studij - Računarstvo i matematika

4. semestar Ne predaje se
Izborni predmet 3, 4, 5, 6 - Redovni Studij - Računarstvo i matematika
Termini konzultacija:
  • izv. prof. Nina Kamčev:

    četvrtkom, 15h-17h u uredu 306, uz najavu mailom

    Lokacija: 306

Obavijesti