PředmětyPředměty(verze: 806)
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
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.
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
  • Sylabus -
    Poslední úprava: (15.05.2013)

    • 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