PředmětyPředměty(verze: 902)
Předmět, akademický rok 2022/2023
   Přihlásit přes CAS
Kombinatorika a grafy 2 - NDMI012
Anglický název: Combinatorics and Graph Theory 2
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2021
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2 [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
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
Neslučitelnost : NDMX012
Záměnnost : NDMX012
Je neslučitelnost pro: NDMA002, NDMI032, NDMX012
Je záměnnost pro: NDMI032, NDMX012, NDMA002
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
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: doc. RNDr. Vít Jelínek, Ph.D. (11.02.2022)

Podmínky získání zápočtu: Zisk alespoň 30 bodů, kde body lze získat řešením domácích úkolů (aspoň 4 série úkolů, každá za aspoň 13 bodů) nebo aktivní účastí na cvičení.

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: 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