PředmětyPředměty(verze: 821)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Kombinatorika a grafy II - NDMI012
Anglický název: Combinatorics and Graph Theory II
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017 do 2017
Semestr: zimní
E-Kredity: 6
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. RNDr. Vít Jelínek, Ph.D.
Mgr. Tereza Klimošová, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Diskrétní matematika
Anotace -
Poslední úprava: T_KAM (10.04.2011)

Přehledová přednáška o klasických výsledcích v kombinatorice a teorii grafů. Předpokládají se znalosti v rozsahu NDMI011 nebo NDMA001.
Podmínky zakončení předmětu
Poslední úprava: Mgr. Tereza Klimošová, Ph.D. (12.10.2017)

Podmínky získání zápočtu na cvičeních V. Jelínka: pro nárok na zápočet je potřeba získat alespoň 25 bodů za řešení domácích úkolů a za aktivní účast na cvičeních. Povaha kontroly předmětu vylučuje opravné termíny u zápočtů.

Podmínkou konání zkoušky je zisk zápočtu.

Literatura -
Poslední úprava: PaedDr. Jan Kuchař (04.10.2016)

R. Diestel: Graph theory, 3rd edition, Springer, 2005.

H. Wilf: Generatingfunctionology (https://www.math.upenn.edu/~wilf/DownldGF.html).

  • Videozáznamy přednášek
  • Požadavky ke zkoušce -
    Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (11.10.2017)

    Zkouška má ústní formu, s možností písemné přípravy předcházející vlastnímu ústnímu zkoušení. Požadavky ke zkoušce odpovídají sylabu předmětu v rozsahu, v jakém byl pokryt na přednáškách a cvičeních. Je požadována i schopnost zobecnit a aplikovat získané teoretické znalosti při praktickém řešení kombinatorických úloh.

    Sylabus -
    Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)

    • Tutteho a Petersenova věta
    • Hamiltonovské kružnice, Oreho podmínka, Chvátalův uzávěr
    • Plochy vyššího rodu, zobecněná Eulerova formule, Heawoodova formule
    • Lemma o kontrahovatelné hraně, Tutteho věta o 3-souv. grafech, Kuratowského věta
    • Barevnost grafů, Brooksova věta, Vizingova věta
    • Tutteho polynom: různé definice, význačné body
    • Obyčejné a exponenciální vytvořující funkce
    • Burnsideovo lemma, Pólyova enumerace, příklady aplikací
    • Věta o slunečnici, Erdös-Ko-Radoova věta, Turánova věta
    • Dilworthova věta, pojem perfektních grafů
    • Chordální grafy

     
    Univerzita Karlova | Informační systém UK