Předmět Kombinatorika a grafy I (NDMI011)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NDMI011 - Kombinatorika a grafy I, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Sylabus
1 Odhady faktoriálu a binomických koecientů 1 Počet koster úplneho grafu (nedeterminantový důkaz). 1.5 Vytvořující funkce (chápané jako Taylorovy řady), aplikace 1.5 Konečné projektivní roviny, latinské čtverce, jejich ortogonalita. 1 Dvojí počítání - počet koster Kn-e, Spernerova věta 1 Toky v sítích (minimaxová věta). 1 Hallova věta a aplikace (Birkhoff-von Neumannova věta, doplňování latinských čtvercù). Maximální párování v bipartitním grafu. 1 k-souvislost, Mengerovy věty pro (ne)orientované grafy ve verzích pro vrcholy a hrany. 0.5 Ušaté lemma, struktura 2-souvislých grafù. 1.5 Základní Ramseyovy věty, Ramsey pro p-tice, Schurova věta. 2 Samoopravné kódy, základní pojmy. Hammnigův kód, Hadamardův kód. Existence asymptoticky dobrých kódù (Gilbert-Varshamov). Hammingův a Elias-Bassalygův dolní odhad.Rozšiřující témata: Steinerovy systémy trojic. Maximální počet hran grafu bez K4 a bez K3.
Literatura
Kučera: Kombinatorické algoritmy Matoušek, Nešetřil: Kapitoly z diskrétní matematikyNešetřil: Teorie grafů
Garant
RNDr. Vít Jelínek, Ph.D.doc. RNDr. Jiří Fiala, Ph.D.Mgr. Martin Mareš, Ph.D.