PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Kombinatorika a grafy 2 - NDMX012
Anglický název: Combinatorics and Graph Theory 2
Zajišťuje: Studijní oddělení (32-STUD)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Je zajišťováno předmětem: NDMI012
Garant: prof. Mgr. Zdeněk Dvořák, Ph.D.
doc. RNDr. Vít Jelínek, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Diskrétní matematika
Prerekvizity : {NXXX014, NXXX015, NXXX016, NXXX017, NXXX018, NXXX022, NXXX023, NXXX024, NXXX025, NXXX033}
Neslučitelnost : NDMI012
Záměnnost : NDMI012
Je neslučitelnost pro: NDMI012
Je záměnnost pro: NDMI012
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. Pavel Veselý, Ph.D. (12.02.2023)

Podmínky získání zápočtu: Zápočet bude za zisk alespoň dvou třetin bodů ze standardních úkolů. Body bude možné získat dle uvážení cvičícího i za bonusové úkoly a aktivní účast na cvičeních.

Povaha kontroly předmětu vylučuje opravné termíny u zápočtů.

Zkoušku lze složit i před získáním 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: prof. Mgr. Zdeněk Dvořák, Ph.D. (27.09.2020)

    Párování v obecných grafech.

    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-souvislých grafech, Kuratowského věta.

    Barevnost grafů, Brooksova věta, Vizingova věta.

    Tutteho polynom: různé definice, význačné body, prostor cyklů a řezů grafu.

    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.

    Perfektni grafy, Dilworthova věta.

    Chordální grafy.

     
    Univerzita Karlova | Informační systém UK